关键词： 复杂网络   节点属性   社团检测   非合作博弈   势博弈   纳什均衡  

摘要： 近年来,随着信息时代的发展,越来越多的学者将社团检测应用到社交网络分析、网络可视化、社交关系的推荐系统等具体问题中。社团是由节点和节点之间的连边所构成的聚簇结构。社团结构能够帮助我们更好地检测到网络中内部隐含的信息。面对着爆炸式的数据,如何充分地利用和挖掘这些隐含的数据信息是当前学者们所关注的问题。博弈论是研究游戏玩家之间策略相互作用的理论。它可以用来解释社团在复杂网络中的形成过程。近年来,不少的学者将社团检测和博弈论相结合,将网络社团结构的检测过程建模成社团形成博弈的过程并取得了不错的效果,从而证明了博弈论用于社团检测算法的合理性和有效性。目前大部分社团检测算法往往从网络的拓扑结构出发,而不去考虑节点本身所具备的属性特征。针对这种带属性信息的网络结构,纯拓扑结构的算法无法直接应用。如何有效地融合网络拓扑信息和节点属性信息是解决此类网络进行社团检测的关键。本文对现有的社团检测算法和基于博弈论的社团检测算法进行了分析,提出了基于非合作博弈的社团生成模型,并在模型的基础上将节点属性考虑到社团检测算法中。主要完成了以下内容:(1)现有的避免分辨率极限问题大多数利用网络的局部和全局的结构信息提出加权机制或者是基于拉普拉斯矩阵的特征向量来对网络进行重连,但是这些方法对初始网络的选择并不敏感,通用性不高。本文为了增强目标网络的社团结构使用了一种有效的加权和重连机制,它可以用来缓解传统社团检测领域中存在的“分辨率极限”的问题。(2)目前大多数社团检测算法是基于优化一个事先定义好的目标函数来进行社团检测。本文从博弈论的角度来模拟节点之间的交互,提出基于节点拓扑相似性的收益函数,考虑节点的拓扑相似性会影响节点策略选择的问题,并将加权和重连的网络分成三个部分,严格证明该非合作博弈满足势博弈条件,即存在纳什均衡点。(3)在提出的非合作博弈社团生成模型基础上,利用节点的属性特征构建似然函数,根据节点对的权值邻接矩阵和属性信息最大化似然函数,最终得到节点的社团隶属度向量,从而确定节点所属的社团。

关键词： 属性网络   社团检测   种群交互   网络结构强化   多目标优化  

摘要： 现实世界中众多的复杂系统都可抽象地表示为网络,对网络的研究已经渗透到各个学科领域。网络通常具有社团结构特性,发现网络中的社团结构有助于更好地理解网络系统的结构和功能,挖掘系统的潜在信息和隐藏规律,对一些未知的功能和行为进行预测。在现实世界中存在一些特殊的网络,每个节点具有一个或多个描述其特征的属性,通常称这种网络为属性网络。挖掘属性网络的社团结构不仅仅依赖于网络的拓扑结构,节点的属性信息也是一种重要的信息源,它具有与拓扑结构互补的重要意义。近年来,基于不同的策略,多个领域的研究者们已经提出了许多属性网络社团检测算法,如何综合利用网络的拓扑结构和节点的属性信息,将网络划分为集合内联系密切且具有较多公共属性的节点集是一个具有挑战性的问题。基于此问题,本文提出了一种基于节点属性信息优化网络结构的多目标进化社团检测算法,之后根据其在属性信息嘈杂的网络上出现的性能下降问题,做了进一步研究,提出了基于双种群协同进化平衡拓扑结构和属性信息的多目标进化社团检测算法。本文的主要研究工作如下:(1)本文提出了一种基于节点属性信息优化网络结构的多目标进化社团检测算法(MOEA-AT)。MOEA-AT算法利用进化算法框架从构建的属性相关网络中选择一些边添加到原始网络,增强了社团内节点之间的联系,使网络的社团结构更加明显。之后设计了一种根据拓扑网络变化局部调整社团归属的社团调整策略,从而快速获得子代网络对应的社团划分。MOEA-AT算法在挖掘社团结构的过程中不需要人为设定社团数目,同时避免了线性叠加网络拓扑结构和节点属性信息挖掘社团结构的算法需要指定平衡参数的问题。在不同生成参数的LFR属性网络和真实属性网络上与当前几种优秀的社团检测算法进行比较,实验结果表明,MOEA-AT算法相比于其他算法在优化网络结构,确定社团数目和检测社团精度方面均具有一定的优势。(2)MOEA-AT算法利用节点属性信息优化网络结构的方式在一定程度上综合利用了网络的拓扑结构和节点的属性信息,在拓扑结构不明显的网络上表现出较高的性能,并具有较高的稳定性。然而当属性信息越来越嘈杂时,MOEA-AT的算法出现了性能急剧下降的问题。基于此问题,本文提出了一种基于双种群协同进化平衡拓扑结构和属性信息的多目标进化社团检测算法(MOEA-DP)。在MOEA-DP算法中建立了两个种群,一个种群根据网络拓扑结构挖掘社团,另一个种群根据节点的属性信息挖掘社团。两个种群通过不同的基因重组方法独立进化,每隔一定的代数选择各自种群的非支配个体进行交互,以获得另一个种群挖掘的优异的社团结构信息。在随机属性网络上和真实属性网络上与当前几种优秀的社团检测算法进行比较,实验结果表明,MOEA-DP算法相比于其他算法在网络结构不明显和属性信息嘈杂的网络上均具有一定的优势。

关键词： 时间序列   复杂网络   社团检测   信息粒  

摘要： 波动性是金融时间序列的本质特征之一,该特征对于人们从金融数据中获取有价值的信息至关重要。然而,由于金融时间序列具有高噪声和不稳定的特点,如何对其波动性进行识别仍然是一个具有挑战性的问题。本文从粒复杂网络的角度出发,提出了一种研究该问题的新方法。首先,将数值时间序列构造成信息粒,每个信息粒中的时间序列片段具有相似的波动特征;其次,利用信息粒之间的传递关系,构造粒复杂网络,从而直观地描述不同波动模式之间的传递过程;第三,提出了一种新的社团检测方法,用于对粒复杂网络进行社团划分,将相互间传递频繁的信息粒划分到同一个粒社团;最后,运用马尔可夫链模型分析了不同信息粒社团之间更高层次的转移过程,进一步描述了整个金融时间序列中波动性的大尺度转移情况。将该模型利用上证指数进行验证,有效地获取了金融数据的波动规律,并利用信息粒社团分析了不同的波动模式之间的传递转移过程。因此本文从粒复杂网络的角度出发,对金融时间序列的波动规律进行分析研究,能够有效解决金融时间序列高噪声和不稳定的问题,同时可以从不同的角度对金融时间序列的波动性进行分析。本文的贡献以及创新点主要包括以下几个方面:(1)将时间序列进行信息粒化,创新性的利用模糊聚类方法对具有相似波动情况的时间序列进行聚类,将每个类作为不同的粒节点,类与类之间的转移作为有向边,进而构造粒复杂网络。在粒复杂网络中,信息粒作为网络的节点代表具有相似特征的波动模式,有向加权边代表波动模式的传递过程。粒复杂网络可以对金融时间序列波动模式之间的传递及其波动规律有更直观的描述。(2)提出一种新的有向加权网络社团检测算法。网络中节点间的连接关系包括直接相连与间接相连,本算法将节点间的上述两种相连关系同时考虑在内,并且将复杂网络中节点间距离因素加入到亲密度的计算过程中,提出基于节点间距离的亲密度计算方法。通过改变网络上信息粒节点之间的距离自适应调整节点间的亲密度,进而根据亲密度的值对网络进行社团划分。(3)在信息粒社团划分的基础上,运用马尔可夫链模型进一步讨论金融市场波动模式间的传递过程。本文将每个社团看作马尔可夫链中的不同状态,将社团之间的传递、转移视为马尔可夫链中状态的转移,通过计算每个状态间的转移概率,得到下一时刻最有可能的目标状态。不同的状态对应不同的波动模式,为波动模式分析提供有力依据。

关键词： 社交媒体   用户分类   异质网络   社团检测   多标签  

摘要： 近年来,社交媒体的快速发展为人们获取事件、新闻等信息带来了巨大的便利,成为了人们从事网络活动的重要工具。社交媒体账户作为用户在社交媒体上获取信息、发表言论和沟通交友的重要媒介,包含了大量有价值信息,通过对社交媒体账户进行分析可以有效地将具有共性特征的用户识别为一个集合。有效的用户分类方法不仅可以快速地帮助用户发现感兴趣的信息,同时还能实现可靠的社交媒体管理以及个性化的内容和用户推荐。通常,社交媒体中用户所发送或关注的信息往往来自多个主题,仅仅对这些用户进行单标签分类会漏掉很多其他主题信息,而通过对用户进行多标签分类,可以更加全面地描述用户的多语义属性。然而,现有的多标签分类算法研究大都针对于文本和图片等领域,针对用户进行多标签分类的研究较少。另外,现有的多标签用户分类算法没有实现用户的有效表征,直接将其用于社交媒体场景下难以实现较好的用户分类效果。本文通过对复杂的社交网络进行分析,在对用户进行单标签分类研究的基础之上实现了用户的多标签分类,主要贡献如下:(1)对于用户单标签分类问题,提出了基于异质网络的用户半监督分类方法。在网络构建阶段,考虑到社交媒体中包含了多种信息,通过构建异质网络可以有效地对这些信息进行融合,从而更好地描述真实社交场景。在特征提取阶段,通过分析网络中用户之间交互行为背后的意义,提取了用户关系特征和特殊词频特征;通过分析用户的发推行为,提取了用户实体关系特征。在模型训练阶段,本文借鉴了半监督学习的思想来实现模型的训练,在减少了对训练集需求的同时提升了用户分类的准确性。在实际场景中,通过与现有的一些用户分类方法进行对比,发现本文所提出的算法能有效的提高分类性能。(2)考虑到异质网络在用户分类问题上的有效性,本文在基于异质网络的用户单标签分类方法基础之上,加入了重叠社团检测技术,提出了基于重叠社团检测的用户多标签分类方法。通过对网络中的用户进行重叠社团检测并将社团检测结果用于用户的表征,可以有效地评估一个用户同时属于多个标签的分布情况,同时还能对没有直接相连的用户进行相似度表征。在多标签分类器的选取上,本文选用ML-KNN多标签分类算法来实现模型的训练。在实际场景中,通过与现有的多标签分类方法进行对比,发现该算法能有效的适用于社交媒体用户多标签分类任务。

关键词： 复杂网络分析   动态社团检测   网络演化   网络表示学习  

摘要： 动态复杂网络因其能够建模许多现实世界复杂系统而受到广泛关注。动态网络演化和社团检测是动态复杂网络分析的核心任务。目前已有的动态网络表示学习方法大多只考虑了网络的演化特性以及低阶的结构信息,而忽略了高阶的社团信息。本文利用表示学习技术在捕捉网络演化模式的同时对节点添加社团级的约束,从而提高节点表示能力;随后,基于网络表示设计出面向较大规模网络的动态社团检测模型。本文的主要研究内容如下:首先,探究了社团结构和网络演化特性对动态网络表示的影响,并提出了动态变分自编码模型Com Dyn VAE。该模型利用变分自编码器不仅有效地整合来自低阶的网络结构信息和高阶的社团信息,而且相较于自编码器提升了模型的鲁棒性。同时,在目标函数中添加了网络演化正则项,保证了网络演化的平滑性。该模型有效地提升了动态网络的的节点表示能力。然后,探究了基于网络表示学习的动态社团检测模型的构建,并提出了基于变分自编码器的无监督动态社团检测模型VGRGMM。该模型通过在变分自编码器中引入高斯混合模型来融入节点的社团先验信息,并利用RNN的变体来捕捉网络的演化特性,同时利用变分贝叶斯对模型的参数进行严格的推导,从而直接得到社团检测结果。该模型有效地提升了动态社团检测的精度及动态网络节点表示能力。最后,通过对海洋灾害领域论文互引网络的分析,得出此领域的科研方向划分及科研方向演化。同时通过分析天津大学专利合作网络,得出专利合作网络的演化特征。以进一步印证本文提出模型的有效性。综上,本文针对动态复杂网络社团检测以及演化问题开拓了新思路,扩展了表示学习在动态网络研究中的应用。提出的基于网络表示学习的无监督动态社团检测模型能够有效地提取出较大规模科学文献网络的动态社团划分及演化规律。

关键词： 社交影响力最大化   重叠社团检测   多目标优化   多样性   成本  

摘要： 近年来,社交网络分析成为人们研究的热点,通过社交网络分析,可以挖掘隐藏在网络中的重要信息,其中在社交网络分析中的一个研究热点就是社交影响力最大化问题。然而在这个研究领域中,大部分学者仅仅关注于影响力最大化,而忽视了被影响群体的多样性,而在实际营销中,商家更倾向于选择多样化的目标受众以推广新产品。除此之外,大部分学者在研究社交影响力最大化问题时忽视了节点成本的重要性,对于市场营销而言,在期望获得影响力最大化的同时营销的成本可以最小化。为了解决上述两个重要问题,本文将研究基于重叠社团检测的社交影响力最大化的多目标方法。之所以采用重叠社团检测技术,是因为重叠社团中的重叠点起着“桥梁”的作用,可以使得信息在不同的社团之间传播,因此被影响的节点的分布会更加多样化;同时,利用重叠社团结构信息可以挖掘网络中性价比（影响力/成本）高的节点,为用户提供影响力大成本小的种子节点。因此,本文在社交影响力最大化问题上分别考虑节点多样性和成本,提出了基于重叠社团检测的多样性影响力最大化进化算法和基于重叠社团检测的成本最小化影响力最大化进化算法。本文的主要研究工作如下:（1）本文提出了基于重叠社团检测的多样性影响力最大化进化算法（MOEA-DIM）。在当前的多样性影响力最大化问题中,针对多样性,主要采用节点的类别信息来设计多样性指标,然而在现实中,节点的类别信息很难收集全。为此,本文利用节点的重叠社团结构信息来设计多样性指标,不需要节点的任何类别信息,因而该指标更具有通用性。由于节点的影响力和多样性两个目标之间存在冲突性,本文提出一种多目标优化方法MOEA-DIM来同时优化两个目标。在MOEA-DIM算法中,分别提出了基于重叠社团结构信息的网络归减策略和基于节点随机游走的种群初始化策略来提高算法的搜索效率和加快算法的收敛速度。最后,通过在真实的网络数据集上的实验结果验证了MOEADIM算法的有效性以及所提策略的有效性。（2）本文提出了基于重叠社团检测的成本最小化影响力最大化进化算法（MOEACMIM）。目前,大部分影响力最大化问题的研究工作中没有考虑节点的成本,然而在实际营销中,获得的影响力越大其营销成本也会随之增加。很明显地,节点的影响力和成本之间存在一定的冲突性。为此,本文提出一种多目标优化方法MOEA-CMIM来解决成本最小化影响力最大化的问题。同时,在MOEA-CMIM算法中,提出了基于重叠社团结构信息的种群初始化策略,来加快算法的搜索效率;除此之外,提出的局部搜索策略可以进一步提高该算法的性能。最后,通过真实数据集的实验结果表明了MOEACMIM算法的有效性以及所提策略的有效性。

关键词： 复杂网络   社团结构   聚类检测   节点特性  

摘要： 随着现代网络世界的快速普及,数据挖掘技术也越来越成熟。在此条件下,复杂网络成为了数据挖掘范畴内的热门研究课题。而复杂网络这一课题当中的热点话题之一就是社团检测,聚类分析是其探究的主要技术手段。对复杂网络中的社团结构进行分析可以协助研究人员更深刻地理解复杂网络的结构性能及其演化过程。论文中具体论述了复杂网络的网络模型、聚类分析的基本概念以及常见的社团检测算法。在对复杂网络中的结构和性能进行分析、研究之后,论文针对复杂网络节点特性提出了两个性能更优的社团检测算法,并将其成功地应用到图聚类中。(1)提出了一个基于节点邻近度的社团检测算法—CS-Cluster。该算法用于对带有语义信息的节点进行聚类检测。经过研究发现,大部分复杂网络中的社团检测算法都是在节点拓扑结构方面进行研究、分析而提出的,它们忽略了节点自身的语义特性,这就导致社团检测的结果不准确。基于此现象,论文提出了一个新的概念(节点邻近度)来完成节点间的相异度计算;引入关联度和匹配度的概念完成节点间结构相异度的计算;之后重新定义了初始聚类中心点的选取规则。该方法避免了人为判断带来的弊端,提高了聚类的精确性。最后,CS-Cluster算法使用K-Medoids算法框架完成社团划分,在两个数据集上进行实验,并表明CS-Cluster取得了较好的聚类效果。(2)提出了一个基于节点核心度的重叠社团检测算法—NCD算法。论文首先提出了节点核心度的概念;其次通过使用中心点可扩展原则,依据网络中节点之间能否可以构建三角模型的判定依据,对网络进行初步的重叠社团检测;最后在划分好的社团的基础上对重叠节点进行识别。论文将NCD算法应用在三个标准数据集上进行实验,使用NMI和模块度来对实验结果进行评价。实验结果表明NCD算法可以有效实现重叠社团的检测。

关键词： 社团检测   偏置   随机游走   信号传播   社团结构  

摘要： 复杂网络是从大量现实存在的复杂系统中抽象得到的,网络的整体功能体现在网络中节点间的相互作用上,社团结构是其关键性结构特征。社团对应于系统的功能模块,提取网络的功能模块有助于深层探究复杂网络的内部规律,从复杂网络中检测社团结构具有重要的理论研究意义和实用价值。因此,很多研究者对社团检测进行了研究,进而提出了很多社团检测算法,如基于模块度优化的社团检测算法、基于标签传播的社团检测算法、基于随机游走的社团检测算法等。在对这些算法进行充分研究的基础上,通过模拟随机游走的过程,结合信号传播过程中随着传播距离的增大,信号量会缓慢衰减的思想,提出了一种带偏置的信号传播机制的随机游走的社团检测算法。该算法从网络中选取一个节点作为信号源,随机选择与其相邻的节点作为下一跳节点,将衰减后的信号量传递到该节点,依次迭代并传递信号。考虑到信号的衰减,为每条边设置偏置,对信号传播过程进行限定。通过模拟信号的传播,将网络的每个顶点作为信号源来重复这一过程,得到传播矩阵。然后,为每个顶点添加自环,并结合邻接矩阵以及顶点间的相似性,形成具有新属性的相似性矩阵。根据新属性矩阵和传播矩阵为每个顶点构造属性。最后,使用k-means算法进行聚类,得到高质量的社团结构。为了验证该方法的性能,在10个实际网络数据集以及不同规模的人工合成网络上进行实验。实验结果充分证明,所提算法能够从网络中提取出高质量的社团结构,从而有效地为社团检测领域提供依据。

关键词： 复杂网络   重叠社团   从属度树   分层网络  

摘要： 重叠社团检测一直是复杂网络研究领域的重点和难点。由于真实网络普遍存在层次结构,结合层次性的重叠社团检测方法将更适用于现实世界复杂网络的研究分析,但目前这类方法的研究还比较少。因此,在定义复杂网络节点领导度、从属度概念的基础上,结合网络层次性建立数学模型,提出了新颖的从属度树检测重叠社团算法。该算法根据从属度值建立从属度树,通过划分树发现重叠节点和重叠社团。在人工网络实验中证明了从属度树算法可以结合层次性发现重叠节点,在Dolphin网络和Karate网络上的实验验证了其检测重叠社团结果的可靠性。与已有一些算法比较的结果表明,从属度树算法能找到其他算法不能找到的重叠节点,以扩展模块度和实际社团结构作为从属度树算法划分重叠社团结果的评价指标。新算法的扩展模块度值大于对比算法,社团划分结果更接近实际社团结构。

关键词： 世界贸易   网络分析   社团检测   中国  

摘要： 随着网络分析方法的发展,利用社团检测和社交网络分析研究世界贸易网络成为当前重要的前沿问题。但目前国内外的研究多为短期尺度,中长期尺度研究亟需更新。当前世界经济发展不确定性要素增多,“一带一路”建设正进入深耕细作的阶段,分析20世纪80年代以来国际政治经济局势的转变以及发达国家与发展中国家的地位更替的长尺度变化,有利于揭示世界贸易网络的中长期演变趋势,并为中国“一带一路”建设提供历史启示。论文主要基于国际货币基金组织(IMF)的贸易方向统计数据库(DOTS),首先总结了1980—2018年世界贸易发展3大历史阶段的基本特征,然后研究了20世纪80年代以来的世界贸易网络中组团及国家地位的演变。研究发现:①世界政治经济格局变化和技术进步对世界贸易网络影响深远。20世纪80年代以来资本主义的生产方式由福特制向后福特制的转变、新自由主义的推广、数字技术的大规模发展以及发展中国家的崛起对全球贸易空间格局产生了深远的影响,中国的崛起是全球贸易网络变化重要的力量。②从Top1贸易网络上看,世界贸易格局呈现出“稳中有变”的演化趋势。世界贸易网络中,欧洲部分的德国、法国和俄罗斯组团相对稳定,而英国和意大利组团地位不断下降;美国主导了亚太部分,澳大利亚组团较为稳定,日本组团地位下降。③印度、巴西和南非等发展中国家的崛起,导致世界经济和贸易格局的重大变化,这些国家近年来成为了新兴的区域性贸易中心。④随着经济高速发展,中国在世界贸易中的地位迅速上升,成为了超过美国的世界贸易组团核心。最后,简要讨论了中长期尺度贸易网络研究对“一带一路”建设的历史启示。