通信学报 ›› 2015, Vol. 36 ›› Issue (2): 68-79.doi: 10.11959/j.issn.1000-436x.2015035

• 学术论文 • 上一篇    下一篇

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

郭昆1,郭文忠1,邱启荣2,张歧山2   

  1. 1 福州大学 数学与计算机科学学院,福建 福州 350108
    2 福州大学 管理学院,福建 福州 350108
  • 出版日期:2015-02-25 发布日期:2017-06-27
  • 基金资助:
    国家自然科学基金资助项目;国家自然科学基金资助项目;教育部科学技术研究重点基金资助项目;福建省科技创新平台建设基金资助项目;福建省自然科学基金资助项目;福建省高校杰出青年科学基金资助项目;福建省高等学校新世纪优秀人才支持计划基金资助项目

Community detection algorithm based on local affinity propagation and user profile

Kun GUO1,Wen-zhong GUO1,Qi-rong QIU2,Qi-shan ZHANG2   

  1. 1 College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China
    2 Management School,Fuzhou University,Fuzhou 350108,China
  • Online:2015-02-25 Published:2017-06-27
  • Supported by:
    The National Natural Science Foundation of China;The National Natural Science Foundation of China;The Key Project of Chinese Ministry of Education;The Technology Innovation Platform Project of Fujian Province;The Natural Science Founda-tion of Fujian Province;The Fujian Province High Science Fund for Distinguished Young Scholars;The Program for New Century Excellent Talents in Fujian Province University

摘要:

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

关键词: 社交网络, 近邻传播, 社区识别, 聚类

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

No Suggested Reading articles found!