基于改进LPA算法的去中心化电子商务网络消费者类别划分算法<sup>*</sup>

doi:10.11925/infotech.2096-3467.2022.0795

数据分析与知识发现

2023, Vol. 7

Issue (10): 25-36 https://doi.org/10.11925/infotech.2096-3467.2022.0795

研究论文

本期目录 | 过刊浏览 | 高级检索

基于改进LPA算法的去中心化电子商务网络消费者类别划分算法^*

刘铸¹,钱晓东²(

)

¹兰州交通大学电子与信息工程学院兰州 730070
²兰州交通大学经济管理学院兰州 730070

A Decentralized Classification Algorithm for Online Consumers Based on Improved LPA

Liu Zhu¹,Qian Xiaodong²(

)

¹School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China
²School of Economics & Management, Lanzhou Jiaotong University, Lanzhou 730070, China

摘要
图/表
参考文献
相关文章
Metrics

全文: PDF (1276 KB) HTML ( 14 )
输出: BibTeX | EndNote (RIS)

摘要

【目的】针对LPA算法应用在去中心化电子商务网络消费者类别划分中标签传播距离以及节点相似度判断的不足，提出一种基于改进LPA的类别划分算法。【方法】首先，针对LPA依据共有关系度量节点远近的问题，引入余弦相似度公式度量节点相似度，并构建相似度邻接矩阵，为了符合局部性的特点和减少度量的时间复杂度，引入反查表原理。其次，运用度中心性指标选出初始中心点，并以集聚系数指标为标签更新规则，根据LPA中标签传播特点不符合局部性要求，提出标签传播距离优化公式。【结果】在两种邻居相似度阈值的网络中，改进LPA比传统LPA的类别结构模块度Q值分别提高了0.054和0.145；在不同规模的数据上模块度Q值至多提高了0.092。【局限】 需要主观设定两个参数和使用反查表，时间复杂度与网络规模为平方关系。【结论】改进的LPA能更好地限制标签传播，使得类别内节点相似度更高、类别间节点相似度更低，适用于去中心化电子商务消费者网络。

	服务

	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	刘铸
	钱晓东

关键词 ：去中心化, 电子商务, 消费者网络, 局部性, 标签传播, 类别划分

Abstract：Abstract: [Objective] This paper proposes a classification algorithm based on the improved LPA model,aiming to improve the label propagation distance and node similarity judgment in decentralized e-commerce network consumer classification. [Methods] Firstly, we introduced the cosine similarity formula to measure the similarity of nodes and constructed a similarity adjacency matrix. These steps improved the measurement of node distance according to their shared relationship in the LPA algorithm. We also introduced the principle of a back lookup table to conform to the characteristics of locality and reduce the time complexity. Secondly, we selected the initial center point with the degree centrality index and used the clustering coefficient index to update the label rules. We proposed the label propagation distance optimization formula to make the LPA algorithm meet the locality requirements. [Results] The category structure modularity Q of the improved LPA algorithm was 0.054 and 0.145 higher than the traditional LPA algorithm in the network with two neighbor similarity thresholds. The modular Q value increased up to 0.092 on data of different scales. [Limitations] The paper needs to set two parameters and use the principle of the back lookup table. The relationship between time complexity and network size is square. [Conclusions] The improved LPA can more effectively limit label propagation, which creates higher intra-categories node similarity and lower inter-categories node similarity. It is suitable for analyzing decentralized e-commerce consumer networks.

Key words： Decentralization E-Commerce Consumer Network Locality Tag Propagation Classification

收稿日期: 2022-07-31 出版日期: 2023-03-22

ZTFLH:	TP393
	G350

基金资助:*国家自然科学基金项目(71461017)

通讯作者: 钱晓东，ORCID：0000-0001-6425-7559，E-mail：qianxd@mail.lzjtu.cn。

引用本文:

刘铸, 钱晓东. 基于改进LPA算法的去中心化电子商务网络消费者类别划分算法^*[J]. 数据分析与知识发现, 2023, 7(10): 25-36.
Liu Zhu, Qian Xiaodong. A Decentralized Classification Algorithm for Online Consumers Based on Improved LPA. Data Analysis and Knowledge Discovery, 2023, 7(10): 25-36.

链接本文:

https://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/10.11925/infotech.2096-3467.2022.0795 或 https://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/Y2023/V7/I10/25

Fig.1 $ρ$ 与 $λ$ 的关系

Fig.2 “杠铃网络”拓扑结构

Fig.3 本文算法划分“杠铃网络”类别示意图

Fig.4 LPA划分“杠铃网络”类别示意图

Fig.5 网络拓扑结构（ $ψ$ = 0.95）

Fig.6 网络拓扑结构（ $ψ$ = 0.90）

算法	$Q$
算法	$ψ = 0.95$	$ψ = 0.90$
LPA	0.629	0.478
本文算法	0.683	0.623

Table 1 真实网络

Q

值测试结果

Fig.7 不同规模网络模块度

Fig.8 $Q$ 贡献值分析（ $ψ = 0.95$ ）

Fig.9 $Q$ 贡献值分析（ $ψ = 0.90$ ）

Fig.10 实验结果收敛性分析

Table 2 消费者群体类型

[1]	Dibb S. Market Segmentation: Strategies for Success[J]. Marketing Intelligence & Planning, 1998, 16(7): 394-406.
[2]	Heilman C M, Bowman D. Segmenting Consumers Using Multiple-Category Purchase Data[J]. International Journal of Research in Marketing, 2002, 19(3): 225-252. doi: 10.1016/S0167-8116(02)00077-0
[3]	曾小青, 徐秦, 张丹, 等. 基于消费数据挖掘的多指标客户细分新方法[J]. 计算机应用研究, 2013, 30(10): 2944-2947.
[3]	(Zeng Xiaoqing, Xu Qin, Zhang Dan, et al. New Multi-Indicator Customer Segmentation Method Based on Consuming Data Mining[J]. Application Research of Computers, 2013, 30(10): 2944-2947.)
[4]	胡凤英, 周正龙. 考虑社交关系的网购拼单研究[J]. 中国管理科学, 2021, 29(11): 191-202.
[4]	(Hu Fengying, Zhou Zhenglong. Online Interpersonal Group-Buying Based on Social Relationship[J]. Chinese Journal of Management Science, 2021, 29(11): 191-202.)
[5]	Jarukasemratana S, Murata T, Liu X. Community Detection Algorithm Based on Centrality and Node Distance in Scale-Free Networks[C]// Proceedings of the 24th ACM Conference on Hypertext and Social Media. 2013: 258-262.
[6]	Shang C X, Feng S Z, Zhao Z Y, et al. Efficiently Detecting Overlapping Communities Through Seeding and Semi-Supervised Learning[J]. International Journal of Machine Learning and Cybernetics, 2017, 8(2): 455-468. doi: 10.1007/s13042-015-0338-5
[7]	Huang J B, Sun H L, Liu Y G, et al. Towards Online Multiresolution Community Detection in Large-scale Networks[J]. PLoS One, 2011, 6(8): e23829.
[8]	吴建, 王梓权, 易亿, 等. 基于图遍历的局部社区发现算法[J]. 计算机应用研究, 2019, 36(9): 2636-2638, 2670.
[8]	(Wu Jian, Wang Ziquan, Yi Yi, et al. Local Community Detection Algorithm Based on Graph Traversal[J]. Application Research of Computers, 2019, 36(9): 2636-2638, 2670.)
[9]	Raghavan U N, Albert R, Kumara S. Near Linear Time Algorithm to Detect Community Structures in Large-scale Networks[J]. Physical Review E, Statistical, Nonlinear and Soft Matter Physics, 2007, 76(3 Pt 2): 036106.
[10]	Leung I X Y, Hui P, Liò P, et al. Towards Real-Time Community Detection in Large Networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2009, 79(6 Pt 2): 066107.
[11]	张蕾, 钱峰, 赵姝, 等. 基于边权的稳定标签传播社区发现算法[J]. 小型微型计算机系统, 2019, 40(2): 314-319.
[11]	(Zhang Lei, Qian Feng, Zhao Shu, et al. Stable Label Propagation Algorithm Based on Edge Weights for Community Detection[J]. Journal of Chinese Computer Systems, 2019, 40(2): 314-319.)
[12]	刘扬, 郑文萍, 张川, 等. 一种基于局部随机游走的标签传播算法[J]. 计算机科学, 2022, 49(10): 103-110. doi: 10.11896/jsjkx.220400145
[12]	(Liu Yang, Zheng Wenping, Zhang Chuan, et al. Local Random Walk Based Label Propagation Algorithm[J]. Computer Science, 2022, 49(10): 103-110.) doi: 10.11896/jsjkx.220400145
[13]	Gregory S. Finding Overlapping Communities in Networks by Label Propagation[J]. New Journal of Physics, 2010, 12(10): 103018. doi: 10.1088/1367-2630/12/10/103018
[14]	Attal J P, Malek M, Zolghadri M. Overlapping Community Detection Using Core Label Propagation Algorithm and Belonging Functions[J]. Applied Intelligence, 2021, 51(11): 8067-8087. doi: 10.1007/s10489-021-02250-4
[15]	梁世娇, 柴争义. 基于节点亲密度的标签传播重叠社区发现算法[J]. 云南大学学报(自然科学版), 2020, 42(1): 58-65.
[15]	Liang Shijiao, Chai Zhengyi. Label Propagation Overlapping Community Detection Algorithm Based on Node Intimacy[J]. Journal of Yunnan University(Natural Sciences Edition), 2020, 42(01):58-65.)
[16]	Barber M J, Clark J W. Detecting Network Communities by Propagating Labels under Constraints[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2009, 80(2 Pt 2): 026129.
[17]	Šubelj L, Bajec M. Robust Network Community Detection Using Balanced Propagation[J]. The European Physical Journal B, 2011, 81(3): 353-362. doi: 10.1140/epjb/e2011-10979-2
[18]	Zhou K, Martin A, Pan Q, et al. Evidential Label Propagation Algorithm for Graphs[C]// Proceedings of the 19th International Conference on Information Fusion. IEEE, 2016: 1316-1323.
[19]	Palla G, Derényi I, Farkas I, et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society[J]. Nature, 2005, 435(7043): 814-818. doi: 10.1038/nature03607
[20]	Clauset A. Finding Local Community Structure in Networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2005, 72(2 Pt 2): 026132.
[21]	Aitzhan N Z, Svetinovic D. Security and Privacy in Decentralized Energy Trading Through Multi-Signatures, Blockchain and Anonymous Messaging Streams[J]. IEEE Transactions on Dependable and Secure Computing, 2018, 15(5): 840-852. doi: 10.1109/TDSC.8858
[22]	范吉立, 何蒲, 李晓华, 等. 基于区块链的去中心化物品共享交易服务系统[J]. 计算机应用, 2019, 39(5): 1330-1335. doi: 10.11772/j.issn.1001-9081.2018112512
[22]	(Fan Jili, He Pu, Li Xiaohua, et al. Blockchain Based Decentralized Item Sharing and Transaction Service System[J]. Journal of Computer Applications, 2019, 39(5): 1330-1335.) doi: 10.11772/j.issn.1001-9081.2018112512
[23]	Ge C P, Liu Z, Fang L M. A Blockchain Based Decentralized Data Security Mechanism for the Internet of Things[J]. Journal of Parallel and Distributed Computing, 2020, 141: 1-9. doi: 10.1016/j.jpdc.2020.03.005
[24]	徐志明, 李栋, 刘挺, 等. 微博用户的相似性度量及其应用[J]. 计算机学报, 2014, 37(1): 207-218.
[24]	(Xu Zhiming, Li Dong, Liu Ting, et al. Measuring Similarity between Microblog Users and its Application[J]. Chinese Journal of Computers, 2014, 37(1): 207-218.)
[25]	戴维·诺克, 杨松. 社会网络分析[M]. 李兰, 译. 2版. 上海: 格致出版社, 上海人民出版社, 2012: 103-104.
[25]	(David Knock, Yang Song. Social Network Analysis[M]. Translated by Li Lan. The 2nd Edition. Shanghai: Truth & Wisdom Press, Shanghai People’s Publishing House, 2012: 103-104.)
[26]	Newman M E J. Modularity and Community Structure in Networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23): 8577-8582. doi: 10.1073/pnas.0601602103 pmid: 16723398

[1]	冯勇, 徐文韬, 王嵘冰, 徐红艳, 张永刚. 电商异构网络中基于多层信息融合的用户社区划分算法*[J]. 数据分析与知识发现, 2022, 6(5): 89-98.
[2]	李晓峰,马静,李驰,朱恒民. 基于XGBoost模型的电商商品品名识别算法研究 ^*[J]. 数据分析与知识发现, 2019, 3(7): 34-41.
[3]	张素琪, 高星, 霍士杰, 郭京津, 顾军华. 基于速度优化和社区偏向的标签传播算法^*[J]. 数据分析与知识发现, 2018, 2(3): 60-69.
[4]	吴江, 贺超城, 龚正. 基于加权有向网络熵的2017 NBA总决赛球队去中心化水平与绩效研究[J]. 数据分析与知识发现, 2018, 2(2): 37-45.
[5]	王宇, 李秀秀. 基于电子商务评论的商家信誉维度构建^*[J]. 数据分析与知识发现, 2017, 1(8): 59-67.
[6]	薛福亮, 刘君玲. 基于用户间信任关系改进的协同过滤推荐方法^*[J]. 数据分析与知识发现, 2017, 1(7): 90-99.
[7]	朱鹏, 赵笑笑, 伍薇. 移动电子商务消费者决策偏好影响因素实证研究^*[J]. 数据分析与知识发现, 2017, 1(3): 1-9.
[8]	刘郝霞, 彭商濂. 一种基于邻近节点影响强度标签传播社区发现方法[J]. 现代图书情报技术, 2015, 31(4): 58-64.
[9]	张文君, 王军, 徐山川. 电商用户需求状态的聚类分析——以淘宝网女装为例[J]. 现代图书情报技术, 2015, 31(3): 67-74.
[10]	高劲松, 梁艳琪, 李珂, 肖涟, 周习曼. 面向关联数据的电子商务信用信息服务模型研究[J]. 现代图书情报技术, 2014, 30(6): 8-16.
[11]	孙霄凌, 赵宇翔, 朱庆华. 在线商品评论系统功能需求的Kano模型分析——以我国主要购物网站为例[J]. 现代图书情报技术, 2013, (6): 76-84.
[12]	沈洪洲, 宗乾进, 袁勤俭. 应用Google云消息框架C2DM实现商务信息推送服务[J]. 现代图书情报技术, 2012, 28(6): 78-83.
[13]	李慧, 刘东苏. 消除用户主观评价差异的电子商务信誉模型[J]. 现代图书情报技术, 2012, 28(2): 48-52.
[14]	李聪. 电子商务协同过滤可扩展性研究综述[J]. 现代图书情报技术, 2010, 26(11): 37-41.
[15]	李聪. ECRec: 基于协同过滤的电子商务个性化推荐管理*[J]. 现代图书情报技术, 2009, (10): 34-39.

Viewed

Full text

Abstract

Cited

Shared

Discussed