[1]冯 健,史丹丹,罗香玉,等.利用节点重要度和社团接近度发现社团结构[J].西安科技大学学报,2020,(01):181-186.
 FENG Jian,SHI Dan-dan,LUO Xiang-yu,et al.Discovering community structure using node importance and community proximity[J].Journal of Xi'an University of Science and Technology,2020,(01):181-186.
点击复制

利用节点重要度和社团接近度发现社团结构(/HTML)
分享到:

西安科技大学学报[ISSN:1672-9315/CN:61-1434/N]

卷:
期数:
2020年01期
页码:
181-186
栏目:
出版日期:
2020-02-15

文章信息/Info

Title:
Discovering community structure using node importance and community proximity
文章编号:
1672-9315(2020)01-0181-06
作者:
冯 健1史丹丹2罗香玉1叶 鸥1
(1.西安科技大学 计算机科学与技术学院,陕西 西安 710054; 2.成都天软信息技术有限公司,四川 成都 610041)
Author(s):
FENG Jian1SHI Dan-dan2LUO Xiang-yu1YE Ou1
(1.College of Computer Science and Engineering,Xi'an University of Science and Technology,Xi'an 710054,China; 2.Chengdu Skysoft Information Technology Co.,Ltd.,Chengdu 610041,China)
关键词:
社团发现 层次聚类 节点重要性 社团接近度
Keywords:
community discovery hierarchical clustering node importance community proximity
分类号:
TP 399
文献标志码:
A
摘要:
社团发现能够揭示复杂网络的拓扑结构特性。针对现有社团发现算法社团初始节点选择随机、相似度计算过分依赖节点间共享邻居以及需要事先设定社团个数等问题,依托层次聚类思想提出基于节点重要度和社团接近度的社团划分算法。首先引入节点重要度的定义并给出重要节点的计算模型,根据该模型得到最重要节点作为社团的初始聚类中心; 然后兼顾节点的共享关系和直接影响定义节点的社团接近度,依据社团接近度指标寻找与社团最接近的节点,根据该节点的加入为社团带来的局部模块度增量判断是否将其加入到已有社团。首个社团划分完毕后,重复选取初始聚类中心并构造社团的过程,直到没有可归入社团的节点。在2个典型复杂网络数据集上进行了测试,并与Girvan-Newman算法和Newman快速算法从准确率和模块度进行对比,实验结果表明所提算法在社团数目未知的前提下能够获得更好的社团划分结果。
Abstract:
Community discovery can reveal the topological characteristics of complex networks.For the existing community discovery algorithms,selection of the initial node for a community israndom,similarity calculation is over-reliant to the shared neighbors between nodes,and the numbers of communities needs to be set in advance.To overcome these problems,based on the idea ofhierarchical clustering,a community discovery algorithm based on node importance and community proximity is proposed.Firstly,the definition of node importance is introduced and the calculation model of important nodes is given.According to the model,the most important node is taken as the initial cluster center of a community.Then,the concept of node-community proximity is defined by taking the sharing relationship and direct effect of nodes into account.The node closest to the community should be found according to the node-community proximity index,and whether to add it to the existing community is decided according to the increment of partial modularity brought by the node.After the first community is divided,the process of selecting the initial cluster center and constructing the community is repeated until there are no nodes left.Experiments are carried out on two typical complex network datasets,with a comparison of the accuracy and modularity made between the results by Girvan-Newman algorithm and Newman fast algorithm.The experimental results show that the proposed algorithm can get better result of community division under the premise that the number of communities is unknown.

参考文献/References:

[1] 汪小帆,刘亚冰.复杂网络中的社团结构算法综述[J].电子科技大学学报,2009,38(5):537-543. WANG Xiao-fan,LIU Ya-bing.Overview of algorithms for detecting community structure in complex networks[J].Journal of University of Electronic Science and Technology of China,2009,38(5):537-543. [2]朱庆生,蒋天弘,周明强.基于自然最近邻居的社团检测算法[J].计算机应用研究,2014,31(12):3560-3563. ZHU Qing-sheng,JIANG Tian-hong,ZHOU Ming-qiang.Community detection algorithm based on natural nearest neighbor[J].Application Research of Computers,2014,31(12):3560-3563. [3]Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of National Academy of Sciences of the United States of America,2002,99(12):7821-7826. [4]Kernighan B W,Lin S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal,1970(49):291-307. [5]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113. [6]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-2663. [7]Sales-Pardo M,Guimera R,Moreira A A,et al.Extracting the hierarchical organization of complex systems[J].Proceedings of the National Academy of Sciences of the United States of America,2007,104(39):15224-15229. [8]Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2003,69(6 Pt 2):066133. [9]Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of community hierarchies in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008,10:10008. [10]Luxburg U.A tutorial on spectral clustering[J].Statistics and Computing,2007,17(4):395-416. [11]付立东.一种对分划分的复杂网络社团检测方法[J].西安科技大学学报,2012,32(5):648-651. FU Li-dong.Detecting of communities in complex networks with two partitioning approach[J].Journal of Xi'an University of Science and Technology,2012,32(5):648-651. [12]Zhang H,Qiu B,Giles C L,et al.An LDA-based community structure discovery approach for large-scale social networks[C]//Muresan G,Altiok T,Melamed B,Zeng D.Proceedings of 2007 IEEE Intelligence and Security Informatics,New Brunswick,NJ USA,2007:200-207. [13]黄发良,肖南峰.基于线图与PSO的网络重叠社区发现[J].自动化学报,2011,37(9):1140-1144. HUANG Fa-liang,XIAO Nan-feng.Discovering overlapping communities based on line graph and PSO[J].Acta Automatica Sinica,2011,37(9):1140-1144. [14]李孝伟,陈福才,刘力雄.一种融合节点与链接属性的社交网络社区划分算法[J].计算机应用研究,2013,30(5):1477-1480. LI Xiao-wei,CHEN Fu-cai,LIU Li-xiong.Combined node and link attributes of social network community detection algorithm[J].Application Research of Computers,2013,30(5):1477-1480. [15]Palla G,Derényi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435:814-818. [16]Shen H W,Cheng X Q,Cai K,et al.Detect overlapping and hierarchical community structure in networks[J].Physica A Statistical Mechanics & Its Applications,2009,388(8):1706-1712. [17]Nepusz T,Petróczi A,Ngyessy L,et al.Fuzzy communities and the concept of bridgeness in complex networks[J].Physical Review E,2008,77(2):016107. [18]Fortunato S,Barthelemy M.Resolution limit in community detection[J].Proceedings of the National Academy of Sciences of the United States of America,2007,104(1):36-41. [19]姜雅文,贾彩燕,于 剑.基于节点相似度的网络社团检测算法研究[J].计算机科学,2011,38(7):185-189. JIANG Ya-wen,JIA Cai-yan,YU Jian.Community detection in complex networks based on vertex similarities[J].Computer Science,2011,38(7):185-189. [20]闵 亮,邵良杉,赵永刚.基于节点相似度的社团检测[J].计算机工程与应用,2015,51(9):77-81. MIN Liang,SHAO Liang-shan,ZHAO Yong-gang.Community detection based on node similarity[J].Computer Engineering and Applications,2015,51(9):77-81. [21]冯 健,丁媛媛.基于重叠社区和结构洞度的社会网络结构洞识别算法[J].计算机工程与科学,2016,38(5):898-904. FENG Jian,DING Yuan-yuan.A structural hole identification algorithm in social networks based on overlapping communities and structural hole degree[J].Computer Engineering & Science,2016,38(5):898-904. [22]Clauset A.Finding local community structure in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2005,72(2):026132. [23]Feng J,Shi D D,Luo X Y.An identification method for important nodes based on K-shell[J].Journal of Complex Networks,2018,6(3):342-352. [24]任卓明,刘建国,邵 凤,等.复杂网络中最小K-核节点的传播能力分析[J].物理学报,2013,62(10):466-471. REN Zhuo-ming,LIU Jian-guo,SHAO Feng,et al.Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks[J].Acta Physica Sinica,2013,62(10):466-471. [25]Burt R.Structural holes and good ideas[J].American Journal of Sociology,2004,110(2):349-399.

更新日期/Last Update: 2020-02-15