一种改进的基于相干邻居亲近度的标签传播算法
详细信息 查看官网全文
- 英文论文题名：An Improved Label Propagation Algorithm Based on Coherence Neighborhood Propinquity
- 论文作者：张超 ; 武先强 ; 董荣胜
- 英文论文作者：Zhang Chao ; Wu XianQiang ; Dong RongSheng ; School of Computer Science and Information Security of the Guilin University of Electronic Technology
- 年：2016
- 作者机构：桂林电子科技大学计算机与信息安全学院;
- 论文关键词：社区发现 ; 标签传播算法 ; 相干邻居亲近度 ; 节点间依赖度 ; 核心CNP网络
- 英文论文关键词：Community discovery ; label propagation algorithm ; Coherent Neighborhood Propinquity ; Coherent Neighborhood Dependence ; core CNP network
- 会议召开时间：2016-11-25
- 会议录名称：广西计算机学会2016年学术年会论文集
- 语种：中文
- 分类号：O157.5
- 学会代码：GXJH
- 会议名称：广西计算机学会2016年学术年会
- 会议地点：中国广西南宁
- 主办单位：广西计算机学会
- 学会名称：广西计算机学会
- 页数：9
- 文件大小：703k
- 原文格式：D
- 会议级别：地方
摘要
在CNP-LPA算法基础上,引入节点间依赖度,提出一种改进的CNP-LPA+算法,在预处理阶段结合相干邻居亲近度与节点间依赖度,将依赖度高的节点并入本区域内的核心节点,并在得到的核心CNP网络基础上传播标签,显著提高了社区发现的质量。选取CNP-LPA算法使用的6组社交网络数据集,采用模块度Q评估LPA、CNP-LPA、CNP-LPA+3种算法的划分结果。实验证明CNP-LPA+算法在所有数据集上均取得最高的Q值,有效提高了算法的准确性,并减少了标签传播过程花费的时间。
In this paper, an improved CNP-LPA+ algorithm is proposed. In the pre-processing stage, the nodes with high dependency are integrated into the core nodes of the local region according to the coherent neighborhood propinquity and dependency. The quality of communities was significantly improved by spreading labels on the core CNP network. Six groups of social network datasets were selected, the modularity measure Q is used to evaluate the results of partitioning by LPA, CNP-LPA, CNP-LPA+ algorithms. Experiments show that the CNP-LPA+ algorithm achieves the highest Q value on all data sets, which improves the accuracy of the algorithm and reduces the time spent on the label propagation process.
In this paper, an improved CNP-LPA+ algorithm is proposed. In the pre-processing stage, the nodes with high dependency are integrated into the core nodes of the local region according to the coherent neighborhood propinquity and dependency. The quality of communities was significantly improved by spreading labels on the core CNP network. Six groups of social network datasets were selected, the modularity measure Q is used to evaluate the results of partitioning by LPA, CNP-LPA, CNP-LPA+ algorithms. Experiments show that the CNP-LPA+ algorithm achieves the highest Q value on all data sets, which improves the accuracy of the algorithm and reduces the time spent on the label propagation process.
引文
[1]林友芳,王天宇,唐锐,等.一种有效的社会网络社区发现模型和算法[J].计算机研究与发展,2012,49(2):337-345.
[2]刘大有,金弟,何东晓,等.复杂网络社区挖掘综述[C]//中国agent理论与应用学术会议.2012.
[3]Serrano Má,Bogu?áM,Sagués F.Uncovering the hidden geometry behind metabolic networks.[J].Molecular Biosystems,2011,8(3):843-50.
[4]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):7821-7826.
[5]Capocci A,Servedio V D P,Caldarelli G,et al.Detecting communities in large networks[J].Physica A Statistical Mechanics&Its Applications,2005,352(352):669-676.
[6]Boccaletti S,Latora V,Moreno Y,et al.Complex networks:Structure and dynamics[J].Physics Reports,2006,424(4–5):175-308.
[7]Radicchi F,Castellano C,Cecconi F,et al.Defining and identifying communities in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2004,101(9):2658-63.
[8]Fortunato S.Community detection in graphs[J].Physics Reports,2010,486(3-5):75-174.
[9]Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks.[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2007,76(2).
[10]Zhang Y,Wang J,Wang Y,et al.Parallel community detection on large networks with propinquity dynamics[J].2009.
[11]Lou H,Li S,Zhao Y.Detecting community structure using label propagation with weighted coherent neighborhood propinquity[M]//The Mental representation of grammatical relations/.MIT Press,1982:3095–3105.
[12]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2004,69(2Pt 2):026113-026113.
[13]Zachary W W.An Information Flow Model for Conflict and Fission in Small Groups1[J].Journal of Anthropological Research,1977,33(4):473.
[14]V.Krebs,A network of co-purchased books about U.S.politics,2008[Online].Available:http://www.orgnet.com.
[15]M.Fiedler,Algebraic connectivity of graphs,Czech Math.J.23(98)(1973)298–305.
[16]M.E.J.Newman,The structure of scientific collaboration networks,Proc.Natl.Acad.Sci.USA 98(2001)404–409.
[17]Laboratory for Web Algorithmics.2011.http://law.di.unimi.it/datasets.php
[2]刘大有,金弟,何东晓,等.复杂网络社区挖掘综述[C]//中国agent理论与应用学术会议.2012.
[3]Serrano Má,Bogu?áM,Sagués F.Uncovering the hidden geometry behind metabolic networks.[J].Molecular Biosystems,2011,8(3):843-50.
[4]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):7821-7826.
[5]Capocci A,Servedio V D P,Caldarelli G,et al.Detecting communities in large networks[J].Physica A Statistical Mechanics&Its Applications,2005,352(352):669-676.
[6]Boccaletti S,Latora V,Moreno Y,et al.Complex networks:Structure and dynamics[J].Physics Reports,2006,424(4–5):175-308.
[7]Radicchi F,Castellano C,Cecconi F,et al.Defining and identifying communities in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2004,101(9):2658-63.
[8]Fortunato S.Community detection in graphs[J].Physics Reports,2010,486(3-5):75-174.
[9]Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks.[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2007,76(2).
[10]Zhang Y,Wang J,Wang Y,et al.Parallel community detection on large networks with propinquity dynamics[J].2009.
[11]Lou H,Li S,Zhao Y.Detecting community structure using label propagation with weighted coherent neighborhood propinquity[M]//The Mental representation of grammatical relations/.MIT Press,1982:3095–3105.
[12]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2004,69(2Pt 2):026113-026113.
[13]Zachary W W.An Information Flow Model for Conflict and Fission in Small Groups1[J].Journal of Anthropological Research,1977,33(4):473.
[14]V.Krebs,A network of co-purchased books about U.S.politics,2008[Online].Available:http://www.orgnet.com.
[15]M.Fiedler,Algebraic connectivity of graphs,Czech Math.J.23(98)(1973)298–305.
[16]M.E.J.Newman,The structure of scientific collaboration networks,Proc.Natl.Acad.Sci.USA 98(2001)404–409.
[17]Laboratory for Web Algorithmics.2011.http://law.di.unimi.it/datasets.php