基于广义后缀树的二分网络社区挖掘算法

近年来,二分网络的社区挖掘问题得到了极大的关注。提出了一种基于广义后缀树的二分网络社区挖掘算法。首先从二分网络的邻接矩阵中提取网络中每个节点的链接节点序列,然后构建广义后缀树。广义后缀树的每个节点表示二分网络的一个完全二分团,由此获取并调整完全二分团。通过引入二分团的紧密度得到初始的社区划分,最后再对孤立点进行处理以得到最终的社区划分。所提算法不仅能发现重叠社区,而且能得到一对多关系的社区。在人工数据集和真实数据集上的实验表明,所提算法能准确地识别二分网络中的社区个数,获得很好的划分效果。     

基于信息扩散概率的二分网络社区划分算法

二分网络是复杂网络的表现形式之一,二分网络单侧节点的社区划分对研究复杂网络具有重要的实际意义.基于信息在网络中的扩散概率和模块度思想,本文提出了一个针对二分网络的社区划分聚类算法(IPS算法).该算法通过模拟信息在网络中扩散的过程,利用各个节点的信息量在网络中扩散后,每个节点收到其他节点的信息量作为社区之间合并的依据,并引入二分网络模块度作为社区划分优劣判断的依据.最后算法在典型网络上测试结果表明,该算法不仅能够精确的识别二分网络社区个数,而且可以获得高质量的社区划分结果.     

基于蚁群优化的二分网络社区挖掘

近年来,网络社区挖掘得到了极大的关注,尤其是针对二分网络的社区挖掘。二分网络社区挖掘对于研究复杂网络有非常重要的理论意义和实用价值。提出了一个基于蚁群优化的二分网络社区挖掘算法。该算法首先将二分网络社区挖掘问题转化成一个优化问题,建立一个可供蚂蚁搜索的图模型。同时,根据顶点的拓扑结构定义启发式信息。每只蚂蚁根据每条路径上的信息素和启发式信息选择路径,构造出一个社区的划分,再用二分模块度去衡量社区划分的优劣。实验结果表明,该算法不但可以较准确地识别二分网络的社区数。而且可以获得高质量的社区划分。     

一种基于聚集系数的社区发现算法

社区划分一直是复杂网络研究中的一个热门话题,社区的快速准确划分为研究复杂网络的性质提供了良好的基础。传统的社区发现方法都是在全局复杂网络的基础上进行社区划分,随着网络中节点的增加,网络规模的变大,社区发现变得更为复杂。提出了一种局部社区发现算法,该算法无需知道整个复杂网络的全部信息,只需从一个待求节点出发,考察其与邻接节点的紧密程度,逐步将邻接点添加到社区中,得到该节点所在的社区结构。同时,该算法还可实现全局网络的社区发现。利用该算法分别对Zachary空手道俱乐部网络和海豚社会网络进行社区发现,实验结果表明了该算法的准确性与可行性。     

基于Kullback-Leibler距离的二分网络社区发现方法

现实世界存在大量二分网络,研究二分社区结构有助于从新角度认识和理解复杂网络。由于二分网络特殊的二分结构,使得基于单模网络的现有社区发现算法无法适用。本文提出一种基于Kullback-Leibler距离的二分网络社区发现算法,该算法将异质节点间的连接关系转化为其在用户节点集上的连接概率分布,并建立基于概率分布的KL相似度衡量节点连接模式的差异性,从而克服二分结构对节点相似性评估的不利影响,实现对二分网络异质节点的社区发现。在人工网络和真实网络上的实验和分析表明：该算法能够有效挖掘二分网络社区结构,改善二分网络社区发现的准确性和效率。     

基于图遍历的局部社区发现算法

针对当前局部社区发现算法扩张速度慢不适用于大规模网络的问题,提出了一种基于图遍历的局部社区发现算法。该算法首先找出网络中度数最低的节点,以该节点为起点通过影响力函数将网络中的节点分为社区节点和边界节点,形成初步的社区划分,然后通过适应度函数确定边界节点的社区得到最终划分结果。实验结果表明,该算法在真实网络上进行测试时不仅能够有效地挖掘网络中的社区结构而且具有较快的速度。     

基于连边相似度的重叠社区发现算法研究

针对GN算法在发现重叠社区时存在的不足,以及为了降低算法时间复杂度,提出一种基于网络图中连边相似度划分连边集的重叠社区发现算法EGN。算法依据网络图的连边集进行划分,每一条边被划分到某个特定的社区,而一个节点可以关联多条连边,因此节点可以被划分到不同的社区,从而发现重叠社区。EGN算法首先需要构造网络节点之间连边关系的边图;然后根据边图中节点的关系计算网络图中连边的相似度,在节点之间相似度的基础上提出了连边之间相似度的计算方法;再按照相似度由小到大对边图删除边,构建出边图的树状图。树状图的每一层对应网络的一个划分,采用划分密度函数来衡量划分的质量,以此寻找最优的划分。最后将算法应用到Zachary空手道俱乐部网络中,并与GN算法进行对比,实验结果表明EGN算法能够很好地发现重叠社区。     

边异质网络中的社区结构发现算法

为解决社区结构发现算法功能社区与拓扑社区不一致的问题,提出一种基于边类型相似性聚类(TESC)的社区结构发现算法。该算法以局部拓扑特征与异质信息为目标进行节点聚类,基于节点邻接边类型构造网络节点之间的相似矩阵,从而获取边异质信息。在该相似矩阵的基础上,通过传统层次聚类的思想将相似度大的节点进行合并,进而利用轮廓系数优化社区数量,得到最终社区划分结果。选取社区结构已知的4个真实网络和6个人工合成基准LFR网络,通过与同质网络的GN、Louvain算法以及异质网络的Hete-SPAEM、Hetero-Attractor算法对比,结果表明TESC算法获得的社区结构更接近于网络实际社区结构。     

基于聚类分析的二分网络社区挖掘

针对二分网络中社区挖掘的准确性不高、对额外参数的依赖较大的问题,基于谱聚类算法的思想,从二分网络的拓扑结构展开,提出了一种改进的社区挖掘算法。该算法将二分网络映射到单一网络进行社区挖掘,采用资源分布矩阵替代传统的邻接矩阵,挖掘出同类节点间的隐含信息,有效地保证了原图的信息,改进了谱聚类算法的输入,提高了社区挖掘的准确性;将模块度函数概念应用到聚类分析中,用模块度衡量社区挖掘的质量,有效解决了自动确定聚类数目的问题。在实际网络和人造网络上进行实验,与蚁群优化算法、边集聚系数算法等算法进行对比,实验结果表明,所提算法不但能较准确地获得二分网络的社区数目,且在不需要任何额外参数的情况下,能获得很好的划分效果,可以应用于深入理解二分网络,进行推荐、影响力分析等。     

融入K-核迭代因子的重叠社区发现算法

基于局部扩展的重叠社区发现算法,利用社区的局部扩展特性可有效扩展出重叠社区,但是现有算法存在划分结果不稳定和准确性较低等问题,因此提出了一种基于[K]-核迭代因子和社区隶属度的重叠社区发现算法。该算法引用[K]-核迭代因子的思想,并且与节点密度值相结合,量化节点的影响力,找出节点影响力最大的节点,提高种子节点选择的稳定性和准确性;同时以影响力大的节点为种子节点,通过节点影响力计算得到邻接节点的社区隶属度,根据社区隶属度选择性地添加邻接节点进行社区扩展,提高社区发现的质量。在人工网络图和真实数据集上进行实验,结果表明所提的算法与现有的算法比较具有较高的稳定性和准确性。     

基于节点依赖度和相似社团融合的社团结构发现算法

社团结构作为复杂网络的拓扑特性之一具有重要的理论和实践意义。提出一种基于节点依赖度和相似社团融合的社团结构发现算法,首先根据依赖度和相似度的定义将整个网络划分成若干个平均集聚系数较大的局部网络,构成网络的基础骨架社团;然后根据连接度的定义不断将社团边缘的节点和小社团吸收到相应的骨架网络中去,直到所有节点都得到准确的社团划分。算法在Zachary空手道俱乐部网络和海豚社会网络中进行了社团划分实验,并与GN算法和Newman快速算法进行了比较,结果表明该算法可以有效地划分社团边缘的模糊节点,社团划分结果具有较高的准确度。     

Dual modularity optimization for detecting overlapping communities in bipartite networks

Many algorithms have been designed to discover community structure in networks. These algorithms are mostly dedicated to detecting disjoint communities. Very few of them are intended to discover overlapping communities, particularly the bipartite networks have hardly been explored for the detection of such communities. In this paper, we describe a new approach which consists in forming overlapping mixed communities in a bipartite network based on dual optimization of modularity. To this end, we propose two algorithms. The first one is an evolutionary algorithm dedicated for global optimization of the Newman’s modularity on the line graph. This algorithm has been tested on well-known real benchmark networks and compared with several other existing methods of community detection in networks. The second one is an algorithm that locally optimizes the graph Mancoridis modularity, and we have adapted to a bipartite graph. Specifically, this second algorithm is applied to the decomposition of vertices, resulting from the evolutionary process, and also characterizes the overlapping communities taking into account their semantic aspect. Our approach requires a priori no knowledge on the number of communities searched in the network. We show its interest on two datasets, namely, a group of synthetic networks and real-world network whose structure is also difficult to understand.     

基于拓扑特征的二分网络社团结构划分

目前社团结构划分算法只能划分1类节点并且依赖于额外参数。为此,在分析二分网络社团拓扑特征的基础上,利用社团核与外层的思想,提出一种新的社团结构划分算法。该算法完全依赖于原始网络本身的拓扑结构,并且允许社团间重叠。实验结果表明,该算法无需任何额外参数,即可比较准确地识别实际网络的社团个数,同时划分2类节点的社团结构。     

一种面向度中心性及重叠网络社区的发现算法

针对社会网络中存在较多以度中心节点为中心并且具有多社区重叠节点的网络社区结构,提出了一种面向度中心性及重叠网络社区的两阶段发现算法。第一阶段发现初始社区:选取度最大的Top-k个节点作为候选中心节点,并将每个节点与其邻居节点形成候选初始社区,其中如果某候选社区与已形成的初始社区的重叠度低于阈值,则形成一个新的初始社区;第二阶段调整社区划分:通过偏离度机制进行调整,将偏离度最大值对应的节点划分到连接紧密的相应社区内,形成最终社区划分。实验表明,该方法不仅能够揭示网络中以某个节点为中心的密集的社区结构,还能有效处理初始社区不同程度的重叠问题。相比现有算法,所提方法对预先输入的候选初始社区数k值不敏感,并具有较高的准确性和灵活性。     

基于节点相似性和网络嵌入的复杂网络社区发现算法

社区发现算法对分析复杂网络的拓扑和层次结构、预测复杂网络的演化趋势等具有十分重要的意义.传统的社区发现算法划分精度不高,忽略了网络嵌入的重要性.针对这样的问题,提出了基于节点相似性和网络嵌入Node2Vec方法的无参数社区发现算法.首先,使用网络嵌入Node2Vec方法将网络节点映射成欧氏空间中低维向量表示的数据点,计...     

结合拓扑势与信任度调整的重叠社区发现算法

现实世界中的复杂系统可建模为复杂网络,探究复杂网络中的社区发现算法对于分析复杂网络的拓扑结构和层次结构具有重要作用。早期研究通常将网络中的节点局限在一个社区中,但随着研究的深入发现社区结构呈现重叠特性。针对现有重叠社区发现算法存在划分社区结构不稳定、忽略节点交互和属性等问题,提出一种基于网络拓扑势与信任度调整的重叠社区发现算法。融合节点的属性和结构特征计算节点的拓扑势,依据节点的拓扑势选取核心节点。从核心节点出发构建初始社区群,计算各个社区间的调整信任度,实现社区的合并与再调整,从而识别重叠社区。在多个人工模拟网络和真实网络数据集上的实验结果表明,与基于贪婪派系扩张、种子扩张等的重叠社区发现算法相比,该算法将扩展模块度最高提升至0.719,能有效识别社区结构及重叠节点,提升重叠社区检测性能。