Community detection algorithm based on local affinity propagation and user profile

Kun GUO; Wen-zhong GUO; Qi-rong QIU; Qi-shan ZHANG

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

您当前的位置：

首页 >

文章列表页 >

Community detection algorithm based on local affinity propagation and user profile

Academic papers | 更新时间：2024-06-05

- Community detection algorithm based on local affinity propagation and user profile
- Journal on Communications Vol. 36, Issue 2, Pages: 68-79(2015)
- 作者机构：
  
  1. 福州大学数学与计算机科学学院,福建福州 350108
  2. 福州大学管理学院,福建福州 350108
- 作者简介：
- 基金信息：
  
  TheNationalNaturalScienceFoundationofChina(61103175);The National Natural Science Foundation of China(61300104);The Key Project of Chinese Ministry of Education(212086);The Technology Innovation Platform Project of Fujian Province(2009J10007);The Natural Science Founda-tion of Fujian Province(2013J01230);The Technology Innovation Platform Project of Fujian Province(JA12016);The Fujian Province High School Science Fund for Distinguished Young Scholars(JA13021)
- DOI：10.11959/j.issn.1000-436x.2015035
  CLC： TP393
- Online First：2015-02，
  
  Published：25 February 2015
- 稿件说明：
移动端阅览
Kun GUO, Wen-zhong GUO, Qi-rong QIU, et al. Community detection algorithm based on local affinity propagation and user profile[J]. Journal on Communications, 2015, 36(2): 68-79.
DOI：

Kun GUO, Wen-zhong GUO, Qi-rong QIU, et al. Community detection algorithm based on local affinity propagation and user profile[J]. Journal on Communications, 2015, 36(2): 68-79. DOI： 10.11959/j.issn.1000-436x.2015035.

摘要

提出一种将局部近邻传播和考虑用户特征的相似性测度相结合实现社交网络中的社区识别的算法。一方面，通过放松代表点约束条件及限制消息传播范围为节点的局部近邻，算法在降低时间和空间复杂度的同时保持较小的识别精度损失，从而能够适应社交网络挖掘需要；另一方面，通过将节点的拓扑相似度和特征相似度相结合来描述节点的综合相似度，使算法能够适应社交网络采样数据中用户关联信息不完整的情况。通过在人工数据集和真实数据集上的对比实验表明，所提方法不仅具有近似线性的时间复杂度及线性的空间复杂度，而且在网络中的节点关联边信息不完整时仍保持较好的识别精度。

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.

关键词

Keywords

references

杨博 , 刘大有 , 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 .

FORTUNATO S . Community detection in graphs [J ] . Physics Reports , 2010 , 486 ( 3 - 5 ): 75 - 174 .

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 .

NEWMAN M E J . Detecting community structure in networks [J ] . The European Physical Journal B - Condensed Matter , 2004 , 38 ( 2 ): 321 - 330 .

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 .

GUIMERA R . Functional cartography of complex metabolic networks [J ] . Nature , 2005 , 433 ( 7028 ): 895 - 900 .

DUCH J , ARENAS A . Community detection in complex networks using extremal optimization [J ] . Physical Review E , 2005 , 72 ( 2 ): 027104 .

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 .

淦文燕 , 赫南 , 李德毅等 . 一种基于拓扑势的网络社区发现方法 [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 .

何东晓 , 周栩 , 王佐等 . 复杂网络社区挖掘—基于聚类融合的遗传算法 [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 .

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 .

林旺群 , 卢风顺 , 丁兆云等 . 基于带权图的层次化社区并行计算方法 [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 .

杨博 , 刘杰 , 刘大有 . 基于随机网络集成模型的广义网络社区挖掘算法 [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 .

韩毅 , 方滨兴 , 贾焰等 . 基于密度估计的社会网络特征簇挖掘方法 [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 .

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 .

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 .

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 .

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 .

金弟 , 杨博 , 刘杰等 . 复杂网络簇结构探测—基于随机游走的蚁群算法 [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 .

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 .

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 .

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 .

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 .

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 .

BRENDAN J F , DELBERT D . Clustering by passing messages between data points [J ] . Science , 2007 , 315 ( 5814 ): 972 - 976 .

JUDEA P . Probabilistic Reasoning in Intelligent Systems:Networks of Plausible Inference [M ] . Morgan Kaufmann , 1988 .

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 .

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 .

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 .

Views

2089

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Differential privacy protection scheme based on edge betweenness model

Adaptive clustering federated learning via similarity acceleration

Influence maximization algorithm based on social network

Survey of application of machine learning in wireless channel modeling

Social network link prediction method based on subgraph evolution and improved ant colony optimization algorithm

Related Author

Haiping HUANG

Kai WANG

Xiong TANG

Dongjun ZHANG

Suxia ZHU

Binke GU

Guanglu SUN

Xuan WANG

Related Institution

College of Computer, Nanjing University of Posts and Telecommunications

High Technology Research Key Laboratory of Wireless Sensor Network of Jiangsu Province

Heilongjiang Key Laboratory of Intelligent Information Processing and Application

School of Computer Science and Technology, Harbin University of Science and Technology

School of Computer Science and Technology, Donghua University

AI问答

⁰