浏览全部资源
扫码关注微信
1. 福州大学 数学与计算机科学学院,福建 福州 350108
2. 福州大学 管理学院,福建 福州 350108
[ "郭昆(1979-),男,福建福州人,博士,福州大学讲师、硕士生导师,主要研究方向为社交网络数据挖掘、灰色系统理论、决策支持系统等。" ]
[ "郭文忠(1979-),男,福建泉港人,博士,福州大学教授、博士生导师,主要研究方向为智能信息处理、网络计算。" ]
[ "邱启荣(1981-),男,福建仙游人,福州大学博士生,主要研究方向为社会网络。" ]
[ "张歧山(1962-),男,黑龙江绥化人,博士,福州大学教授、博士生导师,主要研究方向为灰色系统、商务智能与系统工程等。" ]
网络出版日期:2015-02,
纸质出版日期:2015-02-25
移动端阅览
郭昆, 郭文忠, 邱启荣, 等. 基于局部近邻传播及用户特征的社区识别算法[J]. 通信学报, 2015,36(2):68-79.
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.
郭昆, 郭文忠, 邱启荣, 等. 基于局部近邻传播及用户特征的社区识别算法[J]. 通信学报, 2015,36(2):68-79. DOI: 10.11959/j.issn.1000-436x.2015035.
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.
提出一种将局部近邻传播和考虑用户特征的相似性测度相结合实现社交网络中的社区识别的算法。一方面,通过放松代表点约束条件及限制消息传播范围为节点的局部近邻,算法在降低时间和空间复杂度的同时保持较小的识别精度损失,从而能够适应社交网络挖掘需要;另一方面,通过将节点的拓扑相似度和特征相似度相结合来描述节点的综合相似度,使算法能够适应社交网络采样数据中用户关联信息不完整的情况。通过在人工数据集和真实数据集上的对比实验表明,所提方法不仅具有近似线性的时间复杂度及线性的空间复杂度,而且在网络中的节点关联边信息不完整时仍保持较好的识别精度。
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.
杨博 , 刘大有 , 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 .
0
浏览量
807
下载量
0
CSCD
关联资源
相关文章
相关作者
相关机构