关键词： DeepWalk   社团检测   聚类  

摘要： 该文提出一种基于Deep Walk的网络社团检测方法。该算法的基本思想是基于图嵌入的Deep Walk方法,利用网络随机游走的方式,把网络结构映射到欧氏空间中,然后利用经典机器学习聚类算法进行聚类,从而得到社团。该文在具有社团标签的网络中进行实验,从实验中验证了这种思想的可行性,取得了显著的效果。

关键词： 隐藏社团   检测算法   HICODE框架   等级结构  

摘要： 社团结构研究在社交网络、生物网络等领域有着重要的应用，而其密集子结构即社团的研究是其重要的组成部分。经典的社团检测算法研究主要包括非重叠社团算法、重叠社团算法以及构建社团的树状等级结构。2013年以来，何琨等人提出了隐藏社团结构的图模型新概念，给出了在真实网络中挖掘隐藏社团结构的算法框架（HiddenCommunity Detection,HICODE）。\n HICODE框架能够找到一些被强社团掩盖的处于深层次的隐藏社团，这些隐藏社团几乎不能被现有的社团检测算法发现。本文在该框架的基础上，将社团等级结构的概念引入进来。在真实世界中，一个社团内部可能包含了多个更小的社团,对等级结构的研究也是社团检测的重要部分。本文对HICODE框架进行了修改，使其支持了带等级结构的基算法（Base Algorithm）。通过在人工数据和真实数据上的实验，验证了使用处于不同等级社团结构进行结构削弱的效果，完善了HICODE框架。另外，还提出了通过在原图和削弱之后的图中抓取社团对应的子图，然后使用基算法进一步在子图中寻找社团内部的子社团结构。这样对于在HICODE中找出的强社团结构和弱社团结构，算法可以分别继续向下寻找社团内部更小的社团。通过在人工合成数据上面进行实验，验证了算法的有效性。最后将算法应用到真实社交网络上，发现能够找出一些由共同属性组成的多层次多等级的社团，其检测准确率明显优于基算法。

关键词： 社团检测   社团结构分析   差分进化   复杂网络  

摘要： 复杂网络的社团结构分析可抽象为一个优化问题,用进化算法求解。进化类算法的一个基本问题是如何把问题的候选解编码到进化个体中。本文将索引局部邻接表示法用于社团检测进化算法的个体表示,把社团结构分析转化为一个整数优化问题。在该个体表示方法的基础上,提出了一种基于差分进化的社团检测算法。在一组合成网络和真实网络上验证了算法性能,并与两种基于遗传算法的典型社团检测进化算法进行了对比。实验结果表明,当网络社团结构较为清晰时,基于差分进化的算法检测到的社团结构具有更好的质量。

关键词： 复杂网络   社团检测   数据挖掘   距离更新   相似度方差  

摘要： 随着科学技术快速发展,人类社会在不断向前迈进,社会中存在的各种事物以及人之间的关系也变得越来越复杂,形成了一个大规模、具有复杂结构的网络(图)。这一系列现象促使复杂网络相关问题的研究成为当今时代的热点问题,在这些问题中社团检测问题是其中的一个重要分支,该问题同时也是数据挖掘与知识发现过程中的重要步骤。发现网络中的社团结构对于揭示网络的本质,更深一步研究事物之间的相互关系有着重要的意义。由于社团结构的普适性,该问题已经渗透到物理学、生物学、社会学等多个学科,激发了各个领域专家的研究兴趣。本文中提出了两个从动力学角度出发进行社团检测的方法,第一种是基于动力同步距离更新的社团检测算法(DDS),该方法首先使用Jaccard距离作为网络中每条边的初始距离,同时把每个节点视为一个社团。然后根据网络固有的拓扑结构,DDS算法以迭代的方式不断更新网络中每条边的距离,直到最终每条边的距离达到稳定状态。在每一次距离更新过程中,我们首先根据当前时刻边上的距离对社团进行合并与分裂,然后使用网络中节点之间的连接关系计算与边的两个端点直接相邻的节点对该边上的距离产生的影响,进而更新边的距离,在每一轮迭代中位于同一社团内的节点之间的距离会不断缩短。本文提出的第二种方法是基于相似度方差的标签传播社团检测算法(SVLPA),该方法是对传统标签传播算法的改进。SVLPA算法首先计算每个节点的相似度方差,并对节点按照相似度方差值降序排序作为节点标签更新顺序。当网络中节点更新自己标签时,如果其邻居节点中有多个出现次数最多的标签,我们在标签出现次数最多的邻居节点中选择与当前节点相似度最大的邻居节点的标签作为当前节点标签。通过引入这两种策略,SVLPA算法在保证近似线性时间复杂度的前提下,克服了传统标签传播算法产生的社团结果不稳定的缺点。最后,分别在大量真实数据集和人工数据集上对本文提出的两个社团检测算法进行实验评估。实验结果表明,本文提出的两个算法可以在不需要任何参数输入的情况下检测出高质量的社团。DDS算法准确地将网络中的社团结构以直观的方式展现出来,同时又可以有效地避免社团划分结果分布“极端”的情况。SVLPA算法在保证原始标签传播算法时间效率的前提下,从网络中检测出稳定而又准确的社团结构。通过在Ring网络上的实验更进一步说明本文提出的两个算法不会受“分辨率极限”问题的影响。

关键词： 复杂网络   社团检测   模块密度   化学反应优化算法  

摘要： 随着社会科技的迅速发展,复杂系统已经遍布我们生活的方方面面。复杂网络作为复杂系统的一种抽象表现形式而存在,它通常可以抽象为图的形式,即把节点表示为对象,节点之间的连线表示节点之间存在的一定联系。而社团结构又是复杂网络的一个重要特性。一般情况下,社团内部的节点之间连接比较紧密,社团之间的节点连接都比较稀疏。因此发现复杂网络内部的社团结构,对理解网络的拓扑结构和作用具有非常重要的意义。复杂网络社团结构划分算法主要是发现复杂网络中真实存在的社团结构,研究人员提出了一系列的算法来检测复杂网络中潜在的社团结构,以便更好地分析复杂网络。传统社团发现算法大多选择模块度作为社团结构的评判函数,近年来有关研究表明模块度存在一定的分辨率问题,为了解决该问题,有关研究人员提出了模块密度作为新的社团评判函数。本文选择模块密度作为社团结构的评判函数,采用化学反应算法,提出了一种新的社团结构检测算法。本文主要工作及创新点如下:(1)研究了复杂网络社团的评判函数及其相关的一些社团结构发现算法。社团结构作为复杂网络的一个重要方面,研究者提出了很多发现算法,寻求最优划分方法一直是研究重点。论文研究了相关算法各自的优点及缺点。(2)研究了化学反应优化算法。化学反应优化算法是计算机领域与化学领域相结合而孕育出来的,是一种元启发式算法。该算法模拟了化学反应中分子与分子间的相互作用,通过寻找整个分子集中的最小分子势能得到最优解。(3)提出了基于化学反应算法优化模块密度的复杂网络社团检测算法。本文利用模块密度作为适应度函数,采用化学反应优化算法,设计实现了单分子撞墙反应算子、单分子分解反应算子、多分子交换反应算子和多分子合成反应算子。实验结果表明,与几种经典的算法相比,所提算法划分结果更加精确高效。(4)引入精英保留策略,从而提高算法的收敛速度。在化学反应算法中,由于分子动能的存在,使得原本结构较好的分子在反应过程中改变为相对结构不优的分子。这种现象使分子种群丰富,但有可能在有限的迭代次数中找不到最优解,使得算法收敛速度比较慢。精英保留策略在分子反应前搜寻最低势能分子,保留下来,在下次反应迭代前用势能最低分子替换掉势能最高分子。(5)引入爬山局部搜索算子,提高算法局部搜索能力。化学反应优化算法具有良好的全局搜索能力,为了提高其局部搜索能力,在算法中加入爬山法局部搜索法作为局部搜索算子,使得算法更加精确高效。

关键词： 网络可视化   网络压缩   聚类   社团检测   重叠社团   幂图  

摘要： 近年来,复杂网络分析研究表明大量现实网络如社交网络、交通运输网络、引文网络、蛋白质网络、规则关联网络等具有非平凡的拓扑特征。复杂网络分析的主要目标是检测并发现这些结构以有利于人们理解其中蕴含的规律。网络可视化是实现上述目标的重要支撑技术,也是信息可视化的分支研究领域。快速、高效地、多尺度地可视化这些网络拓扑,降低研究复杂性,以供网络分析专家高效浏览并直观发现网络中隐含的规律或趋势,已成为当前重要的研究课题。随着网络规模的快速膨胀,网络结构复杂多样,传统网络可视化方法已经难以满足实际需求。为此,本课题致力于大规模网络的可视化技术研究,将其分解为“网络结构特征检测——网络结构展示”两个阶段,解决如下四个方面的具体问题:(1)大规模网络中重叠社团结构的快速检测;(2)网络拓扑中高阶依赖关系的检测和刻画;(3)大规模网络全局拓扑结构的多尺度展示;(4)局部高密度网络的精确展示。具体研究工作如下:1.针对现有重叠社团挖掘算法易将重叠区域错误地划分为独立的社团且计算复杂的问题,提出了一种基于局部信息度量的快速重叠社团挖掘算法。首先,为节点定义局部信息度量指标——社团连接度和邻居连接度,建模节点与社团的关系,缩小计算范围;然后,每次并行地迭代执行缩减、扩展、去重等操作,并更新局部度量指标,通过松弛每次迭代的终止条件,发现近似最优社团集合而不是最优社团,最终算法复杂度为O(7)m(10)n(8)。基于真实的大规模社交网络数据的试验分析表明:与当前流行的重叠社团挖掘算法相比,本文算法在不损失检测质量的前提下,大幅提升了计算效率。2.针对网络数据中高阶关联特性,设计了一种基于进化博弈理论的网络可视化聚类方法。首先采用超图描述网络内节点间的高阶关联特性,其次,将超图聚类的动态过程建模为进化博弈理论,证明了均衡点与优化问题解的一一对应关系,并推导出用于求解聚类的动力学方程,算法无需设定聚类的数目。人工和真实数据集相结合的试验表明:本文算法能够自动确定分簇数目,具有良好的聚类效果以及较强的鲁棒性。3.针对大规模网络全局结构多尺度展示的问题,提出了一种基于非重要节点拆分融合的网络层次压缩算法。该算法首先在定义节点块及其关系的基础上,给出了针对节点块的拓扑结构重要性度量方法;然后,利用资源分配和分流原理,提出了基于节点拆分的拓扑层次聚合机制;最后,通过将网络中每一层的非重要节点块拆分融合到与其相邻的节点块中,实现网络结构的快速压缩。与现有算法相比,本文算法效率较高,而且可以得到更加连贯的层次结构,从而更好实现多尺度展示。4.针对高密度网络中边的精确展示问题,提出面向强连接网络图的无损压缩算法,借助幂图分析技术,将所有具有相同邻居的节点集合汇聚成单个模块(modules)以大幅压缩网络图,连接到某个模块的一条边表明该边与模块内的所有元素都相连。从而,整个图均可以无损地可视化展示。首先,本文证明了含有单个模块的最优幂图问题为NP难问题,进而扩展一般地最优幂图分解计算为NP难问题;其次,在梳理现有整数线性规划模型和约束规划模型等问题的基础上,本文提出了基于回溯策略的波束搜索算法,以使有限的回溯策略提供启发信息,相较于已知启发式方法更快速地得到更优的结果;最后,通过生成的随机无标度图,验证了本文算法的有效性。

关键词： 社团检测   Surprise   密母算法   多层网络   层级合并   二分网络   全局目标  

摘要： 现实生活中很多复杂系统都可以建模成复杂网络从而进行深入研究。社团结构是复杂网络的一个基本性质。寻找复杂网络中隐藏的社团有助于了解网络的功能和网络上其他任务的完成。本文主要研究不同类型网络上的社团检测算法,涉及的网络主要是简单网络、多层网络和二分网络。本文的工作如下所示:1.社团检测可以被建模成优化问题继而进行求解。模块度是简单网络上使用最广泛的目标,我们可以通过最大化模块度来获得划分。然而,模块度受到分辨率的限制,即当网络足够大的时候,通过最大化模块度找不到网络中小的、自然的社团。因此,Aldecoa等人提出了另一个全局优化目标surprise(S),并且通过实验验证了S不受分辨率限制的影响。我们在密母算法的基础上提出了一个通过最大化S来寻找简单网络中社团的算法MA-CD。通过实验我们发现,得到的社团拥有很高的社团密度。同时,最大化S在部分网络上会导致不平衡的划分。我们于是提出了一个简单的社团合并算法MA-CDevised来对实验结果进行校正。在大量网络上,校正前后实验结果的对比说明了MA-CDevised的有效性。2.多层网络上的社团检测算法强调的是综合各个图层的信息继而得到一个相对鲁棒的划分。然而,大部分的社团检测算法都是针对简单网络而设计的,很少有算法是针对多层网络而设计的。我们基于图层合并的思想提出了一个多层网络上的社团检测算法LRCD-BNs。其基本思路是将多层网络上的社团检测问题转化成图层合并问题继而进行解决。首先,我们改进了一个图层合并算法neighaggre。其次,使用neighaggre去寻找多层网络中存在的社团。实际网络上的实验结果说明了相比较于其他图层合并算法,neighaggre可以获得更高的相对熵。此外,我们将LRCD-BNs应用到实际网络和人工网络上。实验结果表明,LRCD-MNs获得的实验结果在模块度上优势很小,然而却有很高的S值。3.二分网络上与社团检测相关的目标很多,但是很少有工作对这些目标进行实验上的比较。二分网络上的社团有两种不同的定义。因此,这些目标可以分为两类。我们希望在标准网络上对比这些目标的性能。我们在密母算法的基础上,针对不同的情况设计了不同的算法,继而在大量的网络上对不同类别的目标进行了实验。通过结果的比较我们找到了在大部分情况下表现最好的目标,同时发现了一些目标的优点和缺点。

关键词： 统计推理   相似性矩阵   压缩感知   社团检测  

摘要： 随着近年来以计算机科学为代表的信息技术爆发式发展,“大数据”时代悄然来临,使研究人员能收集海量数据做大量并且深入的分析研究。特别是现今数据越来越趋于多元化、复杂化,早已不同于以往的单维度数据结构,高维数据、超大型网络和各种不同属性的数据令传统的数据模型难以发挥作用。本文旨在从网络节点的相似性信息以及拓扑信息出发,建立结合多元数据的分析模型,进而挖掘网络的结构信息。在此之上,从人造网络和真实网络两个角度,分别对其结构信息挖掘能力进行有效性检验,并应用于金融时序数据。基于统计推理的多元数据分析模型的应用,能够为时序数据及混合属性数据的结构信息挖掘研究提供一个有效的分析方法。本文的工作主要包含以下两个方面:1)首先是基于统计推理的多元数据分析模型的构建及其有效性分析。介绍数据研究中常用的节点相似性构造方法、定义和思想,阐述本文数据模型中基于压缩感知相似性矩阵的理论推导过程;给出元数据的定义以及元数据的属性信息在基于统计推理的分析模型中的运用方法。并且在计算机合成网络和引文网络数据中分析基于统计推理的多元数据模型的社团结构挖掘结果,同时使用传统的社团算法对比它们在几个常用评价指标下的表现,验证了利用基于统计推理的多元数据分析模型挖掘网络节点社团结构信息的有效性。2)其次是基于统计推理的多元数据分析模型在金融数据集之上的应用研究。介绍本文使用两个的金融数据集:低频时序数据集——美国标准普尔500指数成分股数据集和高频时序数据集——中国上海证券交易所主板股份数据集。低频金融数据的研究中,本文通过基于压缩感知的方法得到相似性矩阵,并将其通过阈值法转化为节点的邻接矩阵,同时与前人算法比较金融网络拓扑信息建立的有效性。之后,通过高频的金融数据利用统计推理的多元数据分析模型详细分析了上证数据中股票节点的社团结构信息,说明了基于金融市场分类学中的股票之间不一定具有高相关性,真实强关联社团中的股票可能来自不同的市场分类之中。

关键词： 社团检测   归属度   链路预测   边图   谱分析  

摘要： 社团结构是复杂网络的重要特征之一,可以用来表达网络的一些功能和特征;链路预测用已知网络拓扑结构特征和节点属性预测两个节点之间产生连边的概率,两者对复杂系统的研究和应用都具有重要的理论和现实意义。为了降低标签传播算法在社团发现中由于随机性引发的聚类结果不稳定的问题,使用社团归属度来确定社团个数和社团初始形状,很大程度上改进了标签传播的随机选择缺点。提出的LPA-CBD(Label Propagation Algorithm Based on Community Belonging Degree,基于社团归属度的标签传播算法)算法首先寻找平均吸引力最大节点的初始社团,然后通过社团归属度来优化或扩大初始社团,在得到网络的初始社团划分后,对剩余节点利用标签传播算法进行标签选择。实验通过在十个真实网络以及3个人工网络上测试,并与经典的LPA、随机游走算法、BGLL算法、GN算法、快速贪心算法、Leading Eigenvector等社团发现算法在社团数量、算法准确度和模块度等评价指标上对比,实验证明LPA-CBD算法在各个指标上表现良好,不仅具有较低的算法复杂度和较高的社团发现质量,并且提高了原始标签传播算法的稳定性。社团结构是网络中普遍存在的拓扑特征之一,许多真实网络的社团结构不但具有层次性,还具有重叠性,目前大多数工作只研究网络的层次性和重叠性的一个方面。Ahn在2010年发表的文章证明了层次性和重叠性是网络社团结构相同现象的两个方面,本文在Ahn的方法的基础上提出了社团检测的新算法:SAoLG(Spectral Analsis of Line Graph,线图的谱分析),将谱分析方法应用到边社团发现上,进行了兼顾层次性和重叠性的社团检测研究,实验中使用的网络有一个标准网络、两个社团结构清晰的网络(空手道俱乐部网络和海豚社交网络)以及四个真实网络,实验结果的评价准则选择模块度modularity、划分密度PD(Partition Density)、社团数目CN(Community Number)、节点覆盖率CR(Coverage Rate)、未覆盖节点数UV(Uncovered Vertices)、节点划分准确率Accuracy、正确划分节点数CDV(Correctly Divided Vertices),实验对比算法分别为Ahn的算法(LC算法)、CPM算法和GN算法,实验结果表明SAoLG算法实现了网络的重叠社团检测并且社团划分的结果优于其他三个经典的社团检测算法。网络的社团结构同样影响着复杂网络链路预测的准确性。利用图的拉普拉斯矩阵的特征向量作为样本空间进行社团结构划分能够收敛到全局最优,是很好的划分社团结构的方法之一。通过引入基于拉普拉斯矩阵的相似度计算方法,提出一种链路预测新算法:LPbSA(Link Prediction based on Spectral Analysis,基于谱分析的链路预测),将对节点提取属性特征进行边的预测转化为直接对边提取属性特征并根据其属性值进行预测。LPbSA算法首先获取网络拉普拉斯矩阵的特征值和特征向量,选择最小非平凡特征向量的维数为2维和3维,分别获取2维和3维最小非平凡特征向量对应的相似度(文中使用角距离、欧式距离以及曼哈顿距离三种相似度),得到网络中所有节点对之间可能存在的边的6个属性,然后使用机器学习算法对边进行分类,分类变量的值为0和1,其中0表示节点对之间无连边,1表示节点对之间有连边,这样就将网络的链路预测问题转换成了对边的分类预测问题,实验在七个真实数据集上分别与基于节点局部信息的相似性指标、基于路径的相似性指标和基于随机游走的相似性指标三类算法共18个相似性指标的链路预测结果作对比,实验结果证明了LPbSA算法的可行性、有效性。

关键词： 复杂网络   金融网络   系统性风险   网络同配性   社团检测  

摘要： 本文基于金融网络结构构建了金融市场风险演化指标,研究对象包括24只金融业股票板块网络、808只中国A股股票网络、44只全球重要股票指数网络。针对这三类网络进行了相关分析、聚类分析和网络分析。三类网络均具有分层特征,重大市场趋势和经济事件会在节点中累积强相关性,造成系统的“稳健却脆弱”。三类网络的聚类特征除了受到相关性影响之外,也会直接受到政策和国际因素的影响。三类网络连通程度会随经济发展状态产生相应转变,当市场连通程度高于基本面发展程度,网络的连通优势便会慢慢积累为系统性风险。24只金融业股票板块网络在同配性与异配性之间波动,整体是同配网络。808只中国A股股票网络具有明显的异配特征。44只全球重要股票指数网络是同配网络。国家在制定宏观经济战略时,既要考虑本国网络的拓扑特征,也要定位好世界金融市场的资源分配状态与发展阶段。不同的市场结构反映了市场不同的功能模块,可以通过研究金融市场网络结构特征和规律,认识和理解不同的市场功能模块,为有效地预警和防范市场风险提供合理的建议。