社交网络中基于模块度最大化的标签传播算法的研究

陈晶; 万云

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

您当前的位置：

首页 >

文章列表页 >

社交网络中基于模块度最大化的标签传播算法的研究

学术论文 | 更新时间：2024-06-05

- 社交网络中基于模块度最大化的标签传播算法的研究
- Research on label propagation algorithm based on modularity maximization in the social network
- 通信学报 2017年38卷第2期页码：25-33
- 作者机构：
  
  1. 燕山大学信息科学与工程学院，河北秦皇岛 066004
  2. 河北省虚拟技术与系统集成重点实验室，河北秦皇岛 066004
- 作者简介：
  
  [ "陈晶（1976-），女，黑龙江哈尔滨人，博士，燕山大学副教授，主要研究方向为社交网络、对等网络和Web服务等。" ]
  [ "万云（1990-），女，山西晋城人，燕山大学硕士生，主要研究方向为社交网络和数据挖据。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61602401);国家自然科学基金资助项目(61472340);河北省自然科学基金资助项目(F2014203192)
- DOI：10.11959/j.issn.1000-436x.2017025
  中图分类号： TP301.6
- 网络出版日期：2017-02，
  
  纸质出版日期：2017-02-25
- 稿件说明：
移动端阅览
陈晶, 万云. 社交网络中基于模块度最大化的标签传播算法的研究[J]. 通信学报, 2017,38(2):25-33.

Jing CHEN, Yun WAN. Research on label propagation algorithm based on modularity maximization in the social network[J]. Journal on communications, 2017, 38(2): 25-33.
陈晶, 万云. 社交网络中基于模块度最大化的标签传播算法的研究[J]. 通信学报, 2017,38(2):25-33. DOI： 10.11959/j.issn.1000-436x.2017025.

Jing CHEN, Yun WAN. Research on label propagation algorithm based on modularity maximization in the social network[J]. Journal on communications, 2017, 38(2): 25-33. DOI： 10.11959/j.issn.1000-436x.2017025.

摘要

提出了一种利用模块度最大化与社区结构属性相结合的社区发现方法。首先，针对基于模块度最大化的标签传播算法中存在的时间复杂度高的问题，引入传播距离参数，依据“先传播，后合并”的原则，降低了社区合并导致整个网络需要更新带来的较高时间复杂度；其次，结合社区结构的概念提出了基于模块度最大化的标签传播算法（CDMM-LPA）；最后，基于网络数据集，验证并分析了 CDMM-LPA 算法的可行性。实验结果表明，CDMM-LPA算法在降低了时间复杂度的同时，获得了较高的模块度值和更加稳定的强社区结构。

Abstract

A kind of community detection method based on the combination of modularity and community structure attributes was proposed.Firstly

updating the whole network after communities merging every time could result in the high time complexity

therefore

introducing propagation distance parameter and “merger going after label propagation” was utilized to reduce time complexity.Secondly

CDMM-LPA algorithm was proposed by combing label propagation with community structure.Finally

empirical analysis on data networks verified the validity of the approaches.The experimental results show that the CDMM-LPA algorithm has a high modularity value and a more stable community structure while reducing the time complexity.

关键词

Keywords

references

刘耀庭 . 社交网络结构研究 [D ] . 杭州:浙江大学 , 2008 .

LIU Y T . Research on social network structure [D ] . Hangzhou:Zhejiang University , 2008 .

SCOTT J . Social network analysis [M ] . London : Sage PublicationPress , 2013 .

KERNIGHAN B W , LIN S . An efficient heuristic procedure for partitioning graphs [J ] . Bell System Technical Journal , 1970 , 49 ( 2 ): 291 - 307 .

POTHEN A , SIMON H D , LIOU K P . Partitioning sparse matrices with eigenvectors of graphs [J ] . SIAM Journal on Matrix Analysis and Applications , 1990 , 11 ( 3 ): 430 - 452 .

NEWMAN M E J . Analysis of weighted networks [J ] . Physical Review E , 2004 , 70 ( 5 ):056131

CLAUSET A , NEWMAN M E J , MOORE C . Finding community structure in very large networks [J ] . Physical Review E , 2004 , 70 ( 6 ):066111

ZHU X , GHAHRAMANI Z . Learning from labeled and unlabeled data with label propagation [R ] . Technical Report CMU-CALD-02-107,Carnegie Mellon University , 2002 .

RAGHAVAN U N , ALBERT R , KUMARA S . Near linear time algorithm to detect community structures in large-scale networks [J ] . Physical Review E , 2007 , 76 ( 3 ):036106

赵卓翔 , 王轶彤 , 田家堂 . 社会网络中基于标签传播的社区发现新算法 [J ] . 计算机研究与发展 , 2011 , 48 ( S3 ): 8 - 15 .

ZHAO Z X , WANG Y T , TIAN J T . A novel algorithm for community discovery in social networks based on label propagation [J ] . Journal of Computer Research and Development , 2011 , 48 ( S3 ): 8 - 15 .

LOU H , LI S H , ZHAO Y X . Detecting community structure using label propagation with weighted coherent neighborhood propinquity [J ] . Physica A , 2013 , 392 : 3095 - 3105 .

GREGORY S , . An algorithm to find overlapping community structure in networks [C ] // Knowledge discovery in databases:PKDD 2007 . 2007 : 91 - 102 .

WU Z H , LIN Y F , GREGORY S . Balanced multi-label propagation for overlapping community detection in social networks [J ] . Journal of Computer Science and Technology , 2012 , 27 ( 3 ): 468 - 479 .

朱牧 , 孟凡荣 , 周勇 . 基于链接密度聚类的重叠社区发现算法 [J ] . 计算机研究与发展 , 2013 , 50 ( 12 ): 2520 - 2530

ZHU M , MENG F R , ZHOU Y . Density-based link clustering algorithm for overlapping community detection [J ] . Journal of Computer Research and Development , 2013 , 50 ( 12 ): 2520 - 2530 .

BARBER M J , CLARK J W . Detecting network communities by propagating labels under constraints [J ] . Physical Review E , 2009 , 80 ( 2 ):026129

LIU X , MURATA T . Advanced modularity-specialized label propagation algorithm for detecting communities in networks [J ] . Physica A:Statistical Mechanics and its Applications , 2010 , 389 ( 7 ): 1493 - 1500 .

LIU W , PELLEGRINI M , WANG X . Detecting communities based on network topology [J ] . Scientific Reports , 2014 , 4 ( 4 ): 5739 - 5739 .

SHANG R H , LUO S , LI Y . Large-scale community detection based on node membership grade and sub-communities integration [J ] . Physica A:Statistical Mechanics and its Applications , 2015 , 428 : 279 - 294 .

RADICCHI F , CASTELLANO C , CECCONI F . Defining and identifying communities in networks [J ] . The National Academy of Sciences of the United States of America , 2004 , 101 ( 9 ): 2658 - 2663 .

浏览量

1028

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据