Computer Science ›› 2018, Vol. 45 ›› Issue (6A): 314-317.

• Network & Communication • Previous Articles     Next Articles

Community Label Detection Algorithm Based on Potential Background Information

SONG Yan-qiu, LI Gui-jun,LI Hui-jia   

  1. School of Management Science and Engineering,Central University of Finance and Economics,Beijing 100081,China
  • Online:2018-06-20 Published:2018-08-03

Abstract: In recent years,community structure analysis has attracted much attention in many fields,which aims to partition nodes in a graph into several clusters,in order to achieve a satisfactory state in which each cluster has a densely connected intra-cluster structure and homogeneous attribute value.Existing methods mainly assume that nodes in graphs are cooperative to optimize a given objective function,but ignore their background information in real-life contexts.Based on potential theory,this paper proposed a new semi-supervised community detection algorithm,which uses the electrostatic field generated by the tag node to determine the label of unlabeled nodes(community label).This paper firstly gave a certain number of nodes to the user-defined label,and then used the sparse linear equations to calculate the label of the remaining nodes,where each node’s label was set to calculate the maximum potential value.By comparing with the existing algorithms,it is showed that the proposed algorithm has a strong detection ability in terms of the real world network and artificial benchmark network.It is also very accurate even through in the case of fuzzy large-scale community structure.

Key words: Background information, Community detection, Complex networks, Labels detection, Potential theory

CLC Number: 

  • TP393
[1]VAN D S M.Graph clustering by flow simulation[D].Utrecht:University of Utrecht,2000.
[2]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[3]FORTUNATO S.Community detection in graphs[J].Physics Reports,2010,486(3):75-174.
[4]NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.
[5]LI H J,DANIELS J J.Social significance of community structure:Statistical view[J].Physical Review E,2015,91(1):012801.
[6]NEWMAN M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences,2006,103(23):8577-8582.
[7]LI H J,WANG Y,WU L Y,et al.Potts model based on a Mar- kov process computation solves the community structure problem effectively[J].Physical Review E,2012,86(1):016109.
[8]李慧嘉,李慧颖,李爱华.多尺度的社团结构稳定性分析[J].计算机学报,2015,38(2):301-312.
[9]SON S W,JEONG H,NOH J D.Random field Ising model and community structure in complex networks[J].The European Physical Journal B-Condensed Matter and Complex Systems,2006,50(3):431-437.
[10]李慧嘉,李爱华,李慧颖.社团结构迭代快速探测算法.计算机学报,2017,40(4):970-984.
[11]WESTON J,LESLIE C,IE E,et al.Semi-supervised protein classification using cluster kernels[J].Bioinformatics,2005,21(15):3241-3247.
[12]MA X,GAO L,YONG X,et al.Semi-supervised clustering algorithm for community structure detection in complex networks[J].Physica A:Statistical Mechanics and its Applications,2010,389(1):187-197.
[13]EATON E,MANSBACH R.A Spin-Glass Model for Semi-Supervised Community Detection[C]∥AAI.2012.
[14]ZHANG Z Y.Community structure detection in complex networks with partial background information[J].Scientific Reports,2013,3(1):3241.
[15]GRADY L.Random walks for image segmentation[J].IEEE transactions on Pattern Analysis and Machine Intelligence,2006,28(11):1768-1783.
[16]ZHANG Q M,L L,WANG W Q,et al.Potential theory for directed networks[J].PloS One,2013,8(2):e55437.
[17]WANG F,ZHANG C.Semisupervised learning based on genera- lized point charge models[J].IEEE Transactions on Neural Networks,2008,19(7):1307-1311.
[18]DOYLE P G,SNELL J L.Random walks and electric networks[M].Mathematical Association of America,1984.
[19]GOLUB G H,VAN LOAN C F.Matrix computations[M].JHU Press,2012.
[20]ZACHARY W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473.
[21]CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical Review E,2004,70(2):066111.
[22]LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.
[23]ROSVALL M,BERGSTROM C T.Maps of random walks on complex networks reveal community structure[J].Proceedings of the National Academy of Sciences,2008,105(4):1118-1123.
[24]LUSSEAU D,NEWMAN M E J.Identifying the role that animals play in their social networks[J].Proceedings of the Royal Society of London B:Biological Sciences,2004,271(Suppl 6):S477-S481.
[1] HE Xi, HE Ke-tai, WANG Jin-shan, LIN Shen-wen, YANG Jing-lin, FENG Yu-chao. Analysis of Bitcoin Entity Transaction Patterns [J]. Computer Science, 2022, 49(6A): 502-507.
[2] WANG Ben-yu, GU Yi-jun, PENG Shu-fan, ZHENG Di-wen. Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning [J]. Computer Science, 2022, 49(5): 170-178.
[3] YANG Xu-hua, WANG Lei, YE Lei, ZHANG Duan, ZHOU Yan-bo, LONG Hai-xia. Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding [J]. Computer Science, 2022, 49(3): 121-128.
[4] PU Shi, ZHAO Wei-dong. Community Detection Algorithm for Dynamic Academic Network [J]. Computer Science, 2022, 49(1): 89-94.
[5] LI Jia-wen, GUO Bing-hui, YANG Xiao-bo, ZHENG Zhi-ming. Disease Genes Recognition Based on Information Propagation [J]. Computer Science, 2022, 49(1): 264-270.
[6] CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure [J]. Computer Science, 2021, 48(9): 244-250.
[7] WANG Xue-guang, ZHANG Ai-xin, DOU Bing-lin. Non-linear Load Capacity Model of Complex Networks [J]. Computer Science, 2021, 48(6): 282-287.
[8] MA Yuan-yuan, HAN Hua, QU Qian-qian. Importance Evaluation Algorithm Based on Node Intimate Degree [J]. Computer Science, 2021, 48(5): 140-146.
[9] YIN Zi-qiao, GUO Bing-hui, MA Shuang-ge, MI Zhi-long, SUN Yi-fan, ZHENG Zhi-ming. Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network [J]. Computer Science, 2021, 48(5): 184-189.
[10] YANG Xu-hua, WANG Chen. Community Detection Algorithm in Complex Network Based on Network Embedding and Local Resultant Force [J]. Computer Science, 2021, 48(4): 229-236.
[11] XU Xin-li, XIAO Yun-yue, LONG Hai-xia, YANG Xu-hua, MAO Jian-fei. Attributed Network Embedding Based on Matrix Factorization and Community Detection [J]. Computer Science, 2021, 48(12): 204-211.
[12] NING Yi-xin, XIE Hui, JIANG Huo-wen. Survey of Graph Neural Network in Community Detection [J]. Computer Science, 2021, 48(11A): 11-16.
[13] PAN Yu, ZOU Jun-hua, WANG Shuai-hui, HU Gu-yu, PAN Zhi-song. Deep Community Detection Algorithm Based on Network Representation Learning [J]. Computer Science, 2021, 48(11A): 198-203.
[14] ZHAO Man-yu, YE Jun. Synchronization of Uncertain Complex Networks with Sampled-data and Input Saturation [J]. Computer Science, 2021, 48(11A): 481-484.
[15] XUE Lei, TANG Xu-qing. Algorithm for Detecting Overlapping Communities Based on Centered Cliques [J]. Computer Science, 2020, 47(8): 157-163.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!