基于势能背景信息的社团标签探测算法

摘要/Abstract

摘要： 近年来,社团结构分析已经引起很多领域的关注,一些探测方法也陆续被提出。然而,其中大多数方法只利用了网络拓扑结构,并没有考虑内在的背景信息。基于离散势能理论,提出了一种新的半监督社团探测方法,利用标记节点产生的静电场来确定未标记节点的标签(社团标号)。首先给一定数目的节点赋予用户定义的标签;然后利用稀疏线性方程组计算余下节点的标签,其中每个节点的标签被设定为计算出的最大势能值;最后将该方法与现有算法进行比较。实验结果表明,所提算法在现实世界网络和人工基准网络上都展现了很强的探测能力,特别是在只具有模糊大规模社团结构的情况下,该算法仍然具有很高的准确性。

关键词: 背景信息, 标签探测, 复杂网络, 社团探测, 势能理论

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

中图分类号:

TP393

宋砚秋, 李桂君, 李慧嘉. 基于势能背景信息的社团标签探测算法[J]. 计算机科学, 2018, 45(6A): 314-317. https://doi.org/

SONG Yan-qiu, LI Gui-jun, LI Hui-jia. Community Label Detection Algorithm Based on Potential Background Information[J]. Computer Science, 2018, 45(6A): 314-317. https://doi.org/

参考文献

[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.

相关文章 15

[1]	郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2]	何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[3]	杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 Complex Network Analysis on Curriculum System of Data Science and Big Data Technology 计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123
[4]	王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[5]	陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[6]	赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[7]	李家文, 郭炳晖, 杨小博, 郑志明. 基于信息传播的致病基因识别研究 Disease Genes Recognition Based on Information Propagation 计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[8]	穆俊芳, 郑文萍, 王杰, 梁吉业. 基于重连机制的复杂网络鲁棒性分析 Robustness Analysis of Complex Network Based on Rewiring Mechanism 计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108
[9]	胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉. 基于复杂网络的全球航空网络结构分析与应用 Analysis and Application of Global Aviation Network Structure Based on Complex Network 计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112
[10]	王学光, 张爱新, 窦炳琳. 复杂网络上的非线性负载容量模型 Non-linear Load Capacity Model of Complex Networks 计算机科学, 2021, 48(6): 282-287. https://doi.org/10.11896/jsjkx.200700040
[11]	马媛媛, 韩华, 瞿倩倩. 基于节点亲密度的重要性评估算法 Importance Evaluation Algorithm Based on Node Intimate Degree 计算机科学, 2021, 48(5): 140-146. https://doi.org/10.11896/jsjkx.200300184
[12]	殷子樵, 郭炳晖, 马双鸽, 米志龙, 孙怡帆, 郑志明. 群智体系网络结构的自治调节:从生物调控网络结构谈起 Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network 计算机科学, 2021, 48(5): 184-189. https://doi.org/10.11896/jsjkx.210200161
[13]	刘胜久, 李天瑞, 谢鹏, 刘佳. 带权图的多重分形度量 Measure for Multi-fractals of Weighted Graphs 计算机科学, 2021, 48(3): 136-143. https://doi.org/10.11896/jsjkx.200700159
[14]	龚追飞, 魏传佳. 基于改进AdaBoost算法的复杂网络链路预测 Link Prediction of Complex Network Based on Improved AdaBoost Algorithm 计算机科学, 2021, 48(3): 158-162. https://doi.org/10.11896/jsjkx.200600075
[15]	龚追飞, 魏传佳. 基于拓扑相似和XGBoost的复杂网络链路预测方法 Complex Network Link Prediction Method Based on Topology Similarity and XGBoost 计算机科学, 2021, 48(12): 226-230. https://doi.org/10.11896/jsjkx.200800026

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed