计算机科学 ›› 2020, Vol. 47 ›› Issue (6A): 102-107.doi: 10.11896/JsJkx.190900170
杨卓璇1, 马源培1, 严冠2
YANG Zhuo-xuan1, MA Yuan-pei1 and YAN Guan2
摘要： 在资本市场中,根据交易者联系的密切程度,可以划分出众多团体,从而产生特定的社团结构。社团结构探测是一项非常重要而具有挑战性的工作,已经引起来自不同领域学者的广泛关注。然而,极少有多项式时间算法能够快速、准确地探测社团结构。基于著名的模块化设计优化理论,用新颖的k强度关系代表两个节点之间的耦合距离这一想法随之产生。社团结构探测算法使用基于k强度矩阵的广义模块度测量。为了得到最优社团数量,一种新颖的无参数结构得以使用,该结构使用特定转移矩阵的特征值之差作为社团划分边界。最后,将此算法应用于基准网络和实际网络,以评估其有效性。理论分析和实证结果表明,该算法可以快速、准确地探测社团,且易于扩展至大型实际网络。
中图分类号:
| [1] NEWMAN M E J.Fast Algorithm for Detecting CommunityStructure in Networks.Physical Review E,2004,69:066133. [2] NEWMAN M E J,GIRVAN M.Finding and Evaluating Community Structure in Networks.Physical Review E,2004,69:026113. [3] NEWMAN M E J.Modularity and Community Structure in Networks.Proc Natl Acad Sci,2006,103:8577-8582. [4] GAREY M R,JOHNSON D S.Computers and Intractability:A Guide to the Theory of NP-Completeness.San Francisco:Freeman,1979. [5] SCOTT J.Social Network Analysis:A Handbook.London:Sage Publications,2000. [6] GIRVAN M,NEWMAN M E J.Community Structure in Social and Biological Networks.Proc Natl Acad Sci,2002,99:7821-7826. [7] ZHANG X S,WANG R S,WANG Y,et al.Modularity Optimization in Community Detection of Complex Networks.Europhysics Letters,2009,87:38002. [8] ZHANG X S,LI Z,WANG R S,et al.A Combinatorial Model and Algorithm for Globally Searching Community Structure in Complex Networks.J.Comb.Optim.,2012,23(4):425-442. [9] RADICCHI F,CASTELLANO C,CECCONI F,et al.Defining and Identifying Communities in Networks.Proc Natl Acad Sci,2004,101(9):2658-2663. [10] LATAPY M,PONS P.Proceedings of the 20th International Symposium on Computer and Information Sciences.Lecture Notes in Computer Science,2005,3733:284-293. [11] KERNIGHAN B W,LIN S,BELL.An Efficient Heuristic Procedure for Partitioning Graphs.System Technical Journal,1970,49:291-307. [12] LI H J,ZHANG X S.Analysis of Stability of Community Structure Across Multiple Hierarchical Levels.Europhysics Letters,2013,103:58002. [13] LI H J,WANG Y,WU L Y,et al.Potts Model Based on a Markov Process Computation Solves the Community Structure Problem Effectively.Physical Review E,2012,86:016109. [14] BRANDES U.An Algorithm to Detect Community by Geodesic Line in Social Networks.International Journal on Advances in Information Sciences and Service Sciences,2006,3:0608255. [15] HUANG L C,YEN T J,CHOU S C T.International Conference on Advances in Social Networks Analysis and Mining//IEEE Computer Society.2011:110-117. [16] MUCHA P J.Community Structure in Time-Dependent,Multiscale,and Multiplex Networkset.Science,2010(328):876-878. [17] GUTTMANN-BECK N,HASSIN.Approximation Algorithms for Minimum K-Cut.Algorithmica,2000(27):198-207. [18] GAREY M R,JONSON D S.Computers and Intractability:A Guide to the Theory of NP-Completeness.San Francisco:Freeman,1979. [19] MAKI D P.Mathematical Models and Applications,with Emphasis on social,life,and Management sciences.San Francisco:Prentice Hall College Div,1973. [20] XIA Z Y,BU Z.Community Detection Based on a Semantic Network.Knowledge-Based Systems,2012(26):30-39. [21] W N E,LI T,VANDEN-EIJNDEN E.Optimal Partition and Effective Dynamics of Complex Networks.Proc Natl Acad Sci,2008,105(23):7907-7912. [22] DANON L,DUCH J,GUILERA D.Comparing Community Structure Identification.J.Stat.Mech,2005,29:P09008. [23] BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast Unfolding of Communities in Large Networks.J.Stat.Mech,2005,10:P10008. [24] ROSVALL M,BERGSTROM C T.Maps of Random Walks on Complex Networks Reveal Community Structure.Proc Natl Acad Sci,2008,105(4):1118-1123. [25] PALLA G,DERENYI I,FARKAS I.Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society.Nature,2005,435:814-818. [26] LI Z P,ZHANG S H,WANG R S,et al.Quantitative Function for Community Detection.Physical Review E,2008,77:036109. [27] LANCICHINETTI A,FORTUNATO S.Community Detection Algorithms:A Comparative Analysis.Physical Review E,2009,80:056117. |
| [1] | 邵玉, 陈崚, 刘维. 独立级联模型下基于最大似然的负影响力源定位方法 Maximum Likelihood-based Method for Locating Source of Negative Influence Spreading Under Independent Cascade Model 计算机科学, 2022, 49(2): 204-215. https://doi.org/10.11896/jsjkx.201100190 |
| [2] | 高吉吉, 岳雪蓉, 陈智斌. 针对经典排序问题的一种新算法的近似比分析 Approximate Ratios Analysis of New Algorithm for Classical Parallel Scheduling 计算机科学, 2021, 48(4): 37-42. https://doi.org/10.11896/jsjkx.200600064 |
| [3] | 姜新文. 哈密顿图判定问题的多项式时间算法 Polynomial Time Algorithm for Hamilton Circuit Problem 计算机科学, 2020, 47(7): 8-20. https://doi.org/10.11896/jsjkx.191200176 |
| [4] | 富坤, 仇倩, 赵晓梦, 高金辉. 基于节点演化分阶段优化的事件检测方法 Event Detection Method Based on Node Evolution Staged Optimization 计算机科学, 2020, 47(5): 96-102. https://doi.org/10.11896/jsjkx.190400072 |
| [5] | 韩忠明, 郑晨烨, 段大高, 董健. 基于多信息融合表示学习的关联用户挖掘算法 Associated Users Mining Algorithm Based on Multi-information Fusion Representation Learning 计算机科学, 2019, 46(4): 77-82. https://doi.org/10.11896/j.issn.1002-137X.2019.04.012 |
| [6] | 金婷, 谭文安, 孙勇, 赵尧. 模糊多目标进化的社会团队形成方法 Social Team Formation Method Based on Fuzzy Multi-objective Evolution 计算机科学, 2019, 46(2): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.02.048 |
| [7] | 徐方, 邓敏, 熊曾刚, 叶从欢, 徐宁. 移动社会网络中基于多维上下文匹配的数据转发算法 Data Forwarding Algorithm Based on Multidimensional Context Matching in Mobile Social Networks 计算机科学, 2019, 46(2): 81-87. https://doi.org/10.11896/j.issn.1002-137X.2019.02.013 |
| [8] | 尹欣红, 赵世燕, 陈晓云. 带偏置的信号传播的随机游走的社团检测算法 Community Detection Algorithm Based on Random Walk of Signal Propagation with Bias 计算机科学, 2019, 46(12): 45-55. https://doi.org/10.11896/jsjkx.190700051 |
| [9] | 宾晟, 孙更新. 基于多关系社交网络的协同过滤推荐算法 Collaborative Filtering Recommendation Algorithm Based on Multi-relationship Social Network 计算机科学, 2019, 46(12): 56-62. https://doi.org/10.11896/jsjkx.181102189 |
| [10] | 胡庆成, 张勇, 邢春晓. 基于有重叠社区划分的社会网络影响最大化方法研究 K-clique Heuristic Algorithm for Influence Maximization in Social Network 计算机科学, 2018, 45(6): 32-35. https://doi.org/10.11896/j.issn.1002-137X.2018.06.005 |
| [11] | 张昱, 高克宁, 于戈. 一种融合节点属性信息的社会网络链接预测方法 Method of Link Prediction in Social Networks Using Node Attribute Information 计算机科学, 2018, 45(6): 41-45. https://doi.org/10.11896/j.issn.1002-137X.2018.06.007 |
| [12] | 付立东,聂靖靖. 基于进化谱分方法的动态社团检测 Dynamic Community Detection Based on Evolutionary Spectral Method 计算机科学, 2018, 45(2): 171-174. https://doi.org/10.11896/j.issn.1002-137X.2018.02.030 |
| [13] | 张林姿, 贾传亮. 基于拓扑路径的网络演化传播机制研究 Study of Propagation Mechanism in Networks Based on Topological Path 计算机科学, 2018, 45(11A): 308-314. |
| [14] | 陆亿红,张振宁,杨雄. 一种基于节点特征向量的复杂网络社团发现算法 Community Structure Detection Algorithm Based on Nodes’ Eigenvectors 计算机科学, 2017, 44(Z6): 419-423. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.094 |
| [15] | 珠杰,洪军建. 基于SDAs的人物关系抽取方法研究 Research on Method of Personal Relation Extraction under SDAs 计算机科学, 2017, 44(Z6): 141-145. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.033 |
|
||
首页