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: Complex networks, Community detection, Background information, Potential theory, Labels detection

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.
[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.
[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] CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure [J]. Computer Science, 2021, 48(9): 244-250.
[2] 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.
[3] MA Yuan-yuan, HAN Hua, QU Qian-qian. Importance Evaluation Algorithm Based on Node Intimate Degree [J]. Computer Science, 2021, 48(5): 140-146.
[4] 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.
[5] 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.
[6] XUE Lei, TANG Xu-qing. Algorithm for Detecting Overlapping Communities Based on Centered Cliques [J]. Computer Science, 2020, 47(8): 157-163.
[7] ZHANG Qin, CHEN Hong-mei, FENG Yun-fei. Overlapping Community Detection Method Based on Rough Sets and Density Peaks [J]. Computer Science, 2020, 47(5): 72-78.
[8] ZHAO Wei-ji,ZHANG Feng-bin,LIU Jing-lian. Review on Community Detection in Complex Networks [J]. Computer Science, 2020, 47(2): 10-20.
[9] YANG Xu-hua,SHEN Min. Community Detection Algorithm Based on Local Similarity of Feature Vectors [J]. Computer Science, 2020, 47(2): 58-64.
[10] WANG Shuai-hui, HU Gu-yu, PAN Yu, ZHANG Zhi-yue, ZHANG Hai-feng, PAN Zhi-song. Community Detection in Signed Networks with Game Theory [J]. Computer Science, 2020, 47(11A): 449-453.
[11] ZHANG Qin, CHEN Hong-mei, FENG Yun-fei. Overlapping Community Detection Method Based on Rough Sets and Distance Dynamic Model [J]. Computer Science, 2020, 47(10): 75-82.
[12] ZHAO Xia, LI Xian, ZHANG Ze-hua, ZHANG Chen-wei. Community Detection Algorithm Combing Community Embedding and Node Embedding [J]. Computer Science, 2020, 47(10): 121-125.
[13] ZHAO Lei, ZHOU Jin-he. ICN Energy Efficiency Optimization Strategy Based on Content Field of Complex Networks [J]. Computer Science, 2019, 46(9): 137-142.
[14] LIU Xiao-dong, WEI Hai-ping, CAO Yu. Modeling and Stability Analysis for SIRS Model with Network Topology Changes [J]. Computer Science, 2019, 46(6A): 375-379.
[15] SHAN Na, LI Long-jie, LIU Yu-yang, CHEN Xiao-yun. Link Prediction Based on Correlation of Nodes’ Connecting Patterns [J]. Computer Science, 2019, 46(12): 20-25.
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .