复杂网络中的社团结构特性研究

被引:0
作者
刘亚冰
机构
[1] 上海交通大学
关键词
复杂网络; 社团结构; 模块度; 随机重连; 度相关特性; 层次性; 重叠性; 若邻网; 实证分析;
D O I
暂无
年度学位
2010
学位类型
硕士
导师
摘要
现代的复杂网络科学极大促进了人们对现实复杂系统的理解。社团结构是复杂网络的一个极其重要的特性,社团结构就是一组其内部节点间联系非常紧密而与网络中的其他部分联系相对比较稀疏的节点的子集。复杂网络中的社团结构研究在社会学、生物学和计算机科学等多个领域都具有很重要的意义。 近年来,针对不同类型的大规模复杂网络,人们提出了很多寻找社团结构的算法。本文首先对最新的社团结构划分算法进行了综述,给出了该领域重要的研究进展。其次,网络的社团结构特性本质上是由网络的几阶度分布决定一直是网络科学领域悬而未决的问题之一。为此,本文采用高阶随机重连方法和社团检测算法进行仿真实验对该问题进行了研究。最后,有针对性地提出了一种基于Louvain的改进新算法,可以用于寻找加权网络中具有重叠性和层次性的社团结构,并利用该算法分析了在线社会网络Wealink的各种特性,重点分析了Wealink社团特性的发展和演化。 本论文所作的主要贡献如下: 1综述了该领域最新的比较有代表性的一些寻找社团结构的算法,重点分析了基于模块度指标的改进算法,能够体现社团层次性和重叠性的新算法,衡量社团划分算法好坏的基准图。最后展望了该领域的未来研究方向。 2在保持网络一阶、二阶和三阶度相关特性不变的情形下,利用随机重连方法和社团检测算法研究了复杂网络的社团结构特性。仿真分析发现保持网络三阶度相关特性不变的随机重连方法所构造的网络则可以很高精度地呈现原有网络的社团特性,从而表明网络的社团结构可以由三阶度相关特性有效地刻画(不需要更高阶)。本文的研究提供了一种网络构造方法,即利用三阶随机重连方法可构造出能够体现真实网络社团结构这一特性的随机网络。 3提出了一种可用于寻找加权网络中社团结构特性的算法,使得新算法能够同时体现出网络中社团的层次性和重叠性,并能够在较短时间内处理大规模的网络数据。其次提出了一种基于微调策略分析动态网络演化中社团特性的算法,能够在网络规模变化不大的前提下对网络高效地进行社团特性的分析。从而为动态网络的社团研究提供了一种较好的途径。最后利用基准图对三种经典算法的优劣性进行了比较。 4利用新算法对在线社会网络Wealink(http://www.wealink.com)的结构特性和动态演化进行了实证分析,其中包含了网络规模、社团结构、重叠性节点、聚类系数和度分布等特性,重点研究了若邻网中社团结构的动态演化。
引用
收藏
页数:82
共 14 条
[1]
复杂网络理论及其应用.[M].汪小帆;李翔;陈关荣编著;.清华大学出版社.2006,
[2]
New Benchmark in Community Detection..Lancichinetti A;Fortunato S;Radicchi F;.http://www. arXiv.org.2009,
[3]
Accuracy and precision of methods for community identification in weighted networks..Y.Fan;M.Li;P.Zhang;J.Wu;Z.Di;.Physica A:Statistical Mechanics and its Applications.2007,
[4]
Evolution of a large online social network.[J].Haibo Hu;Xiaofan Wang.Physics Letters A.2009, 12
[5]
Improved community structure detection using a modified fine-tuning strategy [J].
Sun, Y. ;
Danila, B. ;
Josic, K. ;
Bassler, K. E. .
EPL, 2009, 86 (02)
[6]
Detecting the overlapping and hierarchical community structure in complex networks.[J].Andrea Lancichinetti;Santo Fortunato;János Kertész.New Journal of Physics.2009, 3
[7]
Detection of node group membership in networks with group overlap [J].
Sawardecker, E. N. ;
Sales-Pardo, M. ;
Amaral, L. A. N. .
EUROPEAN PHYSICAL JOURNAL B, 2009, 67 (03) :277-284
[8]
Systematic topology analysis and generation using degree correlations [J].
Mahadevan, Priya ;
Krioukov, Dmitri ;
Fall, Kevin ;
Vahdat, Amin .
ACM SIGCOMM COMPUTER COMMUNICATION REVIEW, 2006, 36 (04) :135-146
[9]
Structure and time evolution of an Internet dating community [J].
Holme, P ;
Edling, CR ;
Liljeros, F .
SOCIAL NETWORKS, 2004, 26 (02) :155-174
[10]
Detecting community structure in networks [J].
Newman, MEJ .
EUROPEAN PHYSICAL JOURNAL B, 2004, 38 (02) :321-330