基于局部近邻传播及用户特征的社区识别算法

doi:10.11959/j.issn.1000-436x.2015035

Abstract

Abstract:

An algorithm based on local affinity propagation and a new similarity measure concerning user profile is proposed.On one hand,by loosening the exemplar constraint and requiring the messages propagate around a node's neighbors,the algorithm achieves lower time and space complexity without too much lost in clustering accuracy,which makes it adaptable to the mining of large-scale social networks.On the other hand,by designing a hybrid similarity measure based on the topological similarity and the profile similarity of the nodes,the algorithm can effectively tackle the situation of the social networks data without complete user relation information.The experimental results on the artificial datasets and the real-world datasets demonstrate that the algorithm not only has near-linear time complexity and linear space complexity,but also retains high detecting accuracy when handling incomplete networks.

Key words: social network, affinity propagation, community detection, clustering

Kun GUO,Wen-zhong GUO,Qi-rong QIU,Qi-shan ZHANG. Community detection algorithm based on local affinity propagation and user profile[J]. Journal on Communications, 2015, 36(2): 68-79.

Figures/Tables 17

References 29

1	杨博, 刘大有, LIU J M 等. 复杂网络聚类方法[J]. 软件学报, 2009,20(1):54-66. YANG B , LIU D Y , LIU J M , et al. Complex network clustering algorithms[J]. Journal of Software, 2009,20(1):54-66.
2	FORTUNATO S . Community detection in graphs[J]. Physics Reports, 2010,486(3-5):75-174.
3	SHIGA M , TAKIGAWA I , MAMITSUKA H . A spectral approach to clustering numerical vectors as nodes in a network[J]. Pattern Recognition, 2011,44(2):236-251.
4	NEWMAN M E J . Detecting community structure in networks[J]. The European Physical Journal B - Condensed Matter, 2004,38(2):321-330.
5	GUIMERA R , SALES-PARDO M , AMARAL L A N . Modularity from fluctuations in random graphs and complex networks[J]. Physical Review E, 2004,70(2):025101.
6	GUIMERA R . Functional cartography of complex metabolic networks[J]. Nature, 2005,433(7028):895-900.
7	DUCH J , ARENAS A . Community detection in complex networks using extremal optimization[J]. Physical Review E, 2005,72(2):027104.
8	SON S W , JEONG H , NOH D . Random field ising model and community structure in complex networks[J]. The European Physical Journal B, 2006,50(3):431-437.
9	淦文燕, 赫南, 李德毅等. 一种基于拓扑势的网络社区发现方法[J]. 软件学报, 2009,20(8):2241-2254. GAN W Y , HAO N , LI Y D , et al. Community discovery method in networks based on topological potential[J]. Journal of Software, 2009,20(8):2241-2254.
10	何东晓, 周栩, 王佐等. 复杂网络社区挖掘—基于聚类融合的遗传算法[J]. 自动化学报, 2010,36(8):1160-1170. HE D X , ZHOU X , WANG Z , et al. Community mining in complex networks — clustering combination based genetic algorithm[J]. Acta Automatica Sinica, 2010,36(8):1160-1170.
11	YE Z Q , ZHANG K , HU S N , et al. A new definition of modularity for community detection in complex networks[J]. Chinese Physics Letters, 2012,29(9):098901.
12	林旺群, 卢风顺, 丁兆云等. 基于带权图的层次化社区并行计算方法[J]. 软件学报, 2012,23(6):1517-1530. LIN W Q , LU F S , DING Z Y , et al. Parallel computing hierachical community approach based on weighted-graph[J]. Journal of Software, 2012,23(6):1517-1530.
13	杨博, 刘杰, 刘大有 . 基于随机网络集成模型的广义网络社区挖掘算法[J]. 自动化学报, 2012,38(5):812-822. YANG B , LIU J , LIU D Y . A random network ensemble model based generalized network community mining algorithm[J]. Acta Automatica Sinica, 2012,38(5):812-822.
14	韩毅, 方滨兴, 贾焰等. 基于密度估计的社会网络特征簇挖掘方法[J]. 通信学报, 2012,33(5):38-48. HAN Y , FANG B X , JIA Y , et al. Mining characteristic clusters:a density estimation approach[J]. Journal on Communications, 2012,33(5):38-48.
15	GIRVAN M , NEWMAN M E J . Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002,99(12):7812-7826.
16	WU F , HUBERMAN B A . Finding communities in linear time:a physics approach[J]. The European Physical Journal B-Condensed Matter, 2004,38(2):331-338.
17	PALLA G , DERENYI I , FARKAS I , et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005,435(7043):814-818.
18	WU Z H , LIN Y F , GREGORY S , et al. Balanced multi-label propagation for overlapping community detection in social networks[J]. Journal of Computer Science and Technology, 2012,27(3):468-479.
19	金弟, 杨博, 刘杰等. 复杂网络簇结构探测—基于随机游走的蚁群算法[J]. 软件学报, 2012,23(3):451-464. JIN D , YANG B , LIU J , et al. Ant colony optimization based on random walk for community detection in complex networks[J]. Journal of Software, 2012,23(3):451-464.
20	WANG X , MOHANTY N , MCCALLUM A . Group and topic discovery from relations and their attributes[J]. Advances in Neural Information Processing Systems, 2006,18:1449.
21	MOSER F , GE R , ESTER M . Joint cluster analysis of attribute and relationship data without a-priori specification of the number of clusters[A]. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD'07)[C]. 2007.510-519.
22	YAN L , ALEXANDRU N M , WOJCIECH G . Topic-link LDA:joint models of topic and author community[J]. Proceedings of the 26th Annual International Conference on Machine Learning[C]. 2009.665-672.
23	YOSHIDA T . Toward finding hidden communities based on user profiles[A]. Proceedings of the 2010 IEEE International Conference on Data Mining Workshops (ICDE'10)[C]. 2010.380-387.
24	MCAULEY J , LESKOVEC J . Learning to discover social circles in ego networks[A]. Proceedings of the 26th Annual Conference on Neural Information Processing Systems 2012[C]. 2012.548-556.
25	BRENDAN J F , DELBERT D . Clustering by passing messages between data points[J]. Science, 2007,315(5814):972-976.
26	JUDEA P . Probabilistic Reasoning in Intelligent Systems:Networks of Plausible Inference[M]. Morgan Kaufmann, 1988.
27	SUMEDHA M L , WEIGT M . Unsupervised and semi-supervised clustering by message passing:soft-constraint affinity propagation[J]. The European Physical Journal B, 2008,66(1):125-135.
28	LANCICHINETTI A , FORTUNATO S . Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E, 2009,80(1):1-8.
29	LANCICHINETTI A , FORTUNATO S . KERTéSZ J.Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics, 2009,11(3):033015.

Metrics

Recommended 0

No Suggested Reading articles found!

数据集	参数
人工数据集	N = 100～1 000 μ = 0.1
	k = 15～50 c = 10～50
	N_r=100
真实数据集
348	N = 227 c = 14 N_r=161
3 437	N = 547 c = 32 N_r=262
107	N = 1 045 c = 9 N_r=576

算法	参数
AP	maxIter = 500,convIter = 50,p = best p
LAP	maxIter = 500,convIter = 50,p = ?1.0,α = 0.5
NEM	α = 0.5,l = 10,k = true k

[1]	Yang GAO, Hongli ZHANG. Survey on community detection method based on random walk [J]. Journal on Communications, 2023, 44(6): 198-210.
[2]	Yu DONG, Youpeng ZHANG. Conflict evidence combination method based on clustering weighting [J]. Journal on Communications, 2023, 44(3): 157-163.
[3]	Jing ZHAO, Jun LI, Chun LONG, Wei WAN, Jinxia WEI, Kai CHEN. Unsupervised detection method of RoQ covert attacks based on multilayer features [J]. Journal on Communications, 2022, 43(9): 224-239.
[4]	Xuan WANG, Yu ZHANG, Junfeng ZHOU, Ziyang CHEN. Influence maximization algorithm based on social network [J]. Journal on Communications, 2022, 43(8): 151-163.
[5]	Ao LI, Cong FENG, Yutong NIU, Shibiao XU, Yingtao ZHANG, Guanglu SUN. Multiview clustering method for view-unaligned data [J]. Journal on Communications, 2022, 43(7): 143-152.
[6]	Rong QIAN, Jianting XU, Kejun ZHANG, Hongyu DONG, Fangyuan XING. Research on HMM based link prediction method in heterogeneous network [J]. Journal on Communications, 2022, 43(5): 214-225.
[7]	Yimin MAO, Dejin GAN, Liefa LIAO, Zhigang CHEN. Parallel division clustering algorithm based on Spark framework and ASPSO [J]. Journal on Communications, 2022, 43(3): 148-163.
[8]	Tao PENG, Wentao ZHONG, Guojun WANG, Entao LUO, Jinbo XIONG, Yining LIU, Wang Hao. Privacy-preserving precise profile matching in mobile social network [J]. Journal on Communications, 2022, 43(11): 90-103.
[9]	Zhongping ZHANG, Sen LI, Weixiong LIU, Shuxia LIU. Outlier detection algorithm based on fast density peak clustering outlier factor [J]. Journal on Communications, 2022, 43(10): 186-195.
[10]	Huiqin WANG, Wenbin HOU, Qingbin PENG, Minghua CAO, Rui HUANG, Ling LIU. Step-by-step classification detection algorithm of SPPM based on K-means clustering [J]. Journal on Communications, 2022, 43(1): 161-171.
[11]	Qiang HU, Jiaji SHEN, Guanghui JING, Junwei DU. Service clustering method based on description context feature words and improved GSDMM model [J]. Journal on Communications, 2021, 42(8): 176-187.
[12]	Chunfu JIA, Ruiqi LI, Yafei WANG. Privacy protection scheme of DBSCAN clustering based on homomorphic encryption [J]. Journal on Communications, 2021, 42(2): 1-11.
[13]	Liu LIU, Jianhua ZHANG, Yuanyuan FAN, Li YU, Jiachi ZHANG. Survey of application of machine learning in wireless channel modeling [J]. Journal on Communications, 2021, 42(2): 134-153.
[14]	Ao LI, Zhuo WANG, Xiaoyang YU, Deyun CHEN, Yingtao ZHANG, Guanglu SUN. Robust multiview subspace clustering method based on multi-kernel low-redundancy representation learning [J]. Journal on Communications, 2021, 42(11): 193-204.
[15]	Ruizhang HUANG,Ruina BAI,Yanping CHEN,Yongbin QIN,Xinyu CHENG,Youliang TIAN. CMDC:an iterative algorithm for complementary multi-view document clustering [J]. Journal on Communications, 2020, 41(8): 155-164.

Community detection algorithm based on local affinity propagation and user profile

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 17

References 29

Related Articles 15

Metrics

Recommended 0