一种有向网络中社团结构划分的启发式算法

复杂网络中的社团发现和探测是当前复杂网络分析领域中的一个热点研究问题,并且具有非常广泛的应用前景。但是,传统的社团划分算法主要以无向、无权网络为对象进行分析,不能够适用于现实世界中更多的有向网络、赋权网络等。以有向网络为研究对象,研究其中的社团划分算法。鉴于前人提出的有向网络中社团划分算法存在着计算时间复杂度问题,引入模拟退火算法对其进行改进,并在改进算法中考虑了节点的网络结构属性。通过对不同规模的计算机生成的有向网络进行算法测试,验证了本文算法的正确性。最后,对一个实际复杂网络进行了社团划分,进一步验证了算法的有效性。     

动态社团发现研究综述

为适应当前动态网络数据的发展,对动态网络中的社团结构进行检测、追踪和预测,对国内外关于动态网络社团发现与演化的相关文献进行了综述。归纳了动态网络的社团发现算法,清晰了社团演化事件的定义,并梳理了社团发现与演化算法的应用场景。通过文献梳理,提出将来动态社团的研究应注重在大数据集上的算法优化、在多语境下的信息挖掘和在多场景下的应用性。     

复杂网络中的社团结构分析算法研究综述

许多实际网络中都存在着社团结构.为了寻找大规模复杂网络中的社团结构,人们提出了很多算法.本文综述了近几年来比较有代表性的一些算法.首先介绍了计算机科学中最有名的谱平分法和Kernighan-Lin算法,然后介绍了社会学中具有代表性的分裂算法和凝聚算法,并着重分析了最新提出来的一种寻找网络中彼此重叠的社团结构的派系过滤算法.最后指出了进一步的研究方向.     

基于节点动态连接度的网络社团划分算法

首先定义了节点动态连接度这一概念,然后介绍了基于节点动态连接度的网络社团划分算法,之后再对其中相关参数的取值范围和社团划分结果之间的关系进行了分析,并以Zachary网络为例验证了分析结论。在此基础上,以dolphins、polbooks和football 3个实际网络为对象,进行了社团划分实验,证明了本算法可通过动态调整参数实现对不同网络的社团划分。最后将实验结果与其他几种常见的社团划分算法结果进行了比较,证明了算法的优势,并对算法中需要注意的一些问题进行了说明。     

基于节点相似性的LFM社团发现算法

传统的局部适应度社团发现算法(LFM)在社团结构模糊的网络中精度下降严重。针对此问题,提出LFMJ算法。利用邻居节点信息和改进的杰卡德系数重构网络,使网络结构更为清楚,社团划分结果更为准确。为验证算法,选择了5种算法在LFR网络和真实网络中进行测试,包括LFMJ、LFM和传统的LPA算法以及性能较好的WT和FUA算法。结果表明:在标准LFR网络中,LFMJ精度高于LFM和LPA,与FUA和WT相当;在真实网络和具有重叠结构的LFR网络中,LFMJ精度优于其他4种算法。     

基于聚类分析的复杂网络中的社团探测

社团结构是复杂网络中普遍存在的一种特征.本文应用改进了的谱分法将网络的社团探测问题转换为聚类分析问题,并将Girvan和Newman提出的模块度函数概念应用到聚类分析的4类算法中进行社团结构的探测,特别提出了一种新的结合模块度的聚类遗传算法.然后用3种类型的网络实验算例验证了本文算法的有效性,并对实验结果进行了比较分析,得出本文提出的新算法在初始化敏感性和准确性方面效果较好.最后指出本文算法的进一步研究方向.     

基于同步理论的股票网络社团识别研究

利用股票价格波动时间序列的相关特性,基于同步理论研究股票网络的社团结构。通过对关联矩阵的谱分析确定股票网络中存在复杂的社团结构。随后,利用基于Kuramoto模型的同步聚类算法对网络节点(股票)进行动态分组,由局部序参量确定算法的收敛性并得到稳定的社团结构。通过与快速社团检测算法的对比验证,表明基于Kuramoto模型的同步聚类算法能够正确得到股票网络的社团结构,且更符合股票的属性分类。     

二分网络社团结构的比较性定义

为了解决二分网络的聚类问题,借鉴单顶点网络社团结构的比较性定义,提出了直接基于原始二分网络社团结构的比较性定义,这个定义允许社团之间存在重叠,并定义了在二分网络中顶点与社团之间的作用力.在不引进额外参数的情况下,设计了基于此定义的二分网络的聚类算法,并将此算法应用于人工网和一些实际网络中,结果表明这个算法可以比较准确地对网络进行聚类,说明该定义是有效的.     

基于共享最近邻探测社团结构的算法

针对经典重叠社团结构发现的派系过滤算法中派系定义过于严格、算法缺乏实用性、时间复杂度高等问题,提出了一种基于共享最近邻的社团结构发现算法. 该算法不仅可以对网络进行社团结构的划分, 而且可以很好地把网络中的桥点找出,算法的时间复杂 度约为O(nhk), 其中n为网络中的节点数,h为核心社团的数目, k为网络中节点的 最大节点度.为了验证该算法的正确率和性能, 把该算法应用到计算机生成网络和真实网络中, 并与著名的社团探测算法——GN算法和NF快速算法进行了比较.实验的结果表明所提出的算法是有效可行的.     

复杂网络中社团发现的快速划分算法

复杂网络中的社团发现是具有重要理论意义和应用价值的研究领域。针对已有谱平分法和分裂法时间复杂度较高、不适用于社团结构未知的大规模网络等问题,本文提出以扩散距离为谱平分依据,以模块度函数为衡量社团结构划分效果的快速划分算法,并进一步说明了扩散距离的收敛性。实验结果表明,与已有的社团发现算法相比,基于扩散距离的快速划分算法能够得到满意度高的社团结构,时间复杂度较低,对稀疏网络和非稀疏网络都能高效求解,从而体现出算法具有较高的鲁棒性。     

多元偏好、社团结构与网络合作涌现仿真研究

在综合考虑复杂社会网络高集聚性、无标度性以及"社团结构"的基础上,依据"囚徒困境"博弈,建立了基于多元偏好的复杂社会网络演化博弈模型,创新性地将节点影响力运用于博弈策略的更新规则中,并利用Matlab平台进行仿真。从宏观特征和微观结构两方面,通过对照仿真实验,系统研究了多元偏好、社会网络的"社团结构"以及外部连接对合作涌现的影响及其作用机理。研究发现,多元偏好特征下社团结构特征影响主体的异质性期望水平;"社团结构"可以促进合作行为的涌现;社团外部影响力对合作涌现的影响与社团规模有关。     

基于谱方法的复杂网络中社团结构的模块度

现实中的大量复杂网络表现出明显的社团结构, 模块度是衡量网络社团结构划分的重要指标函数, 但最常用的NG模块度存在分辨率限制问题, 不能识别出小于一定规模的社团. 文章在谱映射的基础上, 提出了复杂网络社团结构的两种模块度. 改进的表现模块度不仅能够应用于有权网络, 而且部分解决了NG模块度的局限性问题; 内聚模块度以社团内部的内聚度为衡量依据, 从根本上避免了NG模块度和表现模块度可能出现的不恰当划分情况. 最后通过计算机生成的测试网络和两个经典网络, 与NG模块度对比验证了表现模块度和内聚模块度的可行性和有效性.     

城市群交通网络层级结构与组团结构识别

为了深入研究城市群交通网络层次结构与组团结构,本文建立复杂网络层级结构和组团结构识别算法,并以长株潭城市群交通网络为例划分城市群交通网络的层级结构与组团结构。通过对长株潭城市群交通网络的层次结构与组团结构的研究可以得出以下几个重要结论:(1)层级结构和组团结构并不是孤立,二者同时存在的。(2)复杂网络的层次结构和组团结构算法能够有效地、准确地划分城市群层级结构与组团结构。(3)河流等自然地理条件对城市交通网络连通性和交通网络中的层次结构和组团结构有至关重要的影响。     

复杂网络的特征谱及其应用

网络的特征谱与网络的拓扑密切相关，通过研究特征谱可以更好地了解网络的结构涌现和动力学特性。本文总结了近年来在网络特征谱方面的研究进展，首先介绍了3类重要网络模型邻接矩阵的特征谱密度和网络结构的关系及其在网络中心性和二分性中的应用，接着介绍了谱序列中存在的标度不变性和结构涌现，然后介绍了网络Laplacian矩阵的特征谱与网络同步之间的关系以及在分析网络社团结构中的应用，最后指出了进一步研究的方向。     

当前复杂系统研究的几个方向

复杂系统与复杂性科学被誉为21世纪的科学，是吸引跨学科广泛注意的新型交叉科学。简要概述了复杂系统研究的几个重要方向，包括网络同步、网络交通流、新一代信息网络的结构和动力学、演化合作博弈、生物网络复杂性、人类动力学和信息物理学。