关键词： 复杂网络   社团结构   社团检测   多目标优化   knee point   决策策略  

摘要： 现实世界存在大量的复杂系统,这些复杂系统可以抽象描述为复杂网络。近年来,复杂网络引起了不同领域学者的广泛关注。社团结构是描述复杂网络的重要特性之一,通常,社团内部节点之间的连接较为紧密,而社团之间节点的连接较为稀疏。检测社团结构有助于更好地分析复杂网络结构信息并进一步挖掘复杂网络的潜在功能。因此,复杂网络社团检测是一个重要的研究课题,具有重要的理论意义和现实价值。当前,多目标优化算法是解决复杂网络社团检测问题的重要方法之一。本文提出了一种基于knee point的多目标优化社团检测算法并提出两种决策策略,可以帮助决策者从由多目标优化算法得到的众多社团划分中获得最终的理想划分结果。本文的主要研究工作如下：(1)本文提出了一种基于knee point的多目标社团检测算法。当前的多目标优化社团检测算法没有关注搜索过程中出现的关键点,这种关键点可能对应比较好的网络社团划分。为了找到这种潜在的比较好的划分,本文提出了一种基于knee point的多目标优化社团检测算法(KP-Net),该算法可以搜索到Pareto前沿面上的关键点即knee point,这种关键点对应的是潜在的比较好的划分。knee point与其他划分不同,当一个目标函数值减少很小时,会引起另外一个目标函数值大幅度地增加。因此,作为前沿面上的关键点,knee point对应的是潜在的比较好的划分。在扩展的GN基准网络数据集和真实世界网络上进行测试,并与经典的社团检测算法进行比较,实验结果表明,KP-Net算法可以很好地检测到网络社团结构,是一种有效的社团检测算法。(2)本文提出了两种多目标社团检测决策策略。由于多目标优化社团检测算法得到的结果是一组划分而不是单个划分,需要决策者从中选出一个理想的划分结果,这就给决策者的决策工作带来了挑战,如何从这组划分中得到理想划分结果成为一个待解决的问题。当前的多目标优化社团检测算法往往从中选择模块度最大的划分结果作为最终结果,但是模块度最大的划分并不一定对应最好的划分结果。本文提出两种可以获得理想划分的多目标社团检测决策策略。第一种是基于knee point的决策策略,这种决策策略从多目标算法返回的一组划分中选择knee point作为最终划分结果。和其他划分结果相比较,knee point是决策者所感兴趣的解。因此,基于knee point的决策策略选择knee point作为提供给决策者的最终划分结果。第二种是基于多数投票的决策策略,这种决策策略运用多数投票规则,根据多目标优化社团检测算法得到的所有划分产生一个新的网络划分,对于复杂网络中的两个节点来说,如果在得到的这组划分结果中大多数划分将这两个节点划分到同一个社团,那么最终划分结果就将这两个节点划分在同一个社团。在GN基准网络数据集和真实世界网络上的实验结果表明,本文提出的两种决策策略能够从多目标社团检测算法得到的众多划分中获得复杂网络的理想划分。

关键词： 社团结构检测   节点相似度   线性阶时间复杂度   算法稳定  

摘要： 针对目前社团结构检测算法计算量大,准确度低以及算法结果不稳定的问题,在经典Newman快速算法与LPAm算法的基础之上,各取它们的优点相结合,提出了一种基于局部信息的社团检测新算法。算法利用节点度和共享邻居数定义节点相似度,首先根据节点相似度和一个预设节点相似度阈值将网络划分为初始的社团结构,然后依据另一个预设社团数目参数阈值进一步优化社团结构,最后得到精确度较高的社团划分结果。性能分析证明,该算法有着近似线性的时间复杂度。实验结果表明,本文提出的算法相对于GN算法,Newman快速算法和LPAm算法有着更高的准确度,且它是一种结果稳定的算法,对于大型网络的社团结构预测,有着较好的效果,因此,有着较好的实用性。

关键词： 复杂网络   社团结构   社团检测   网络稀疏化   主动学习  

摘要： 现实世界中众多的复杂系统都可抽象地表示为复杂网络,而社团结构是很多复杂网络最为显著的结构特征,其中的社团往往对应于网络的功能单元,从某种程度而言,整个网络的功能往往取决于社团之间的相互作用。通过检测网络的社团结构,可以在中观(mesoscale)结构层面探索网络的性质,研究网络的结构与功能之间的关系。此外,社团结构也能对网络的动力学特性产生重要的影响。因此,社团检测的研究不仅具有重要的理论意义,而且具有重要的实际应用价值,近年来吸引了计算机、物理、生物等多个学科研究人员的广泛关注,已成为复杂网络学科的一个研究热点。本文对已有的社团检测方法进行了深入的分析,针对这些方法中存在的问题与不足,提出了两类共5种社团检测方法。第一类方法关注的是如何从网络中检测得到尽可能精确的、高质量的社团结构,其中包括三种社团检测方法:(1)DBSCD:该方法首先利用一个稀疏化处理过程,从网络中移除可能位于不同社团之间的一些边,使得社团之间的边界变得清晰;接着使用谱二分法,基于网络转移矩阵第二特征向量中元素的符号,将网络分裂为两个子网络;然后在模块度的约束、指导下,以迭代方式使用同样的谱二分法对选中的子网络进行分裂,每一次迭代选中的都是其分裂能使得模块度增量最大的一个子网络。通过这样的持续分裂,得到最终的社团结构。(2)HBSCD:该方法同样先对网络进行稀疏化处理,使社团结构更加突出。接着基于网络转移矩阵第二特征向量中元素的符号,持续将网络分裂为一系列不可再分的子网络,并将每一个子网络当做一个社团,形成初始的社团结构。然后借鉴Fast算法的思想,通过合并其中一些社团得到最终的社团结构。(3)ASSCD:该方法将主动学习技术引入到社团检测的研究中,并与半监督社团检测算法结合,从网络中提取其社团结构。主动学习策略从网络中主动选取对半监督社团检测算法效用最大的顶点,生成高质量的Must-Link和Cannot-Link成对约束的半监督成分;半监督社团检测算法首先利用这些半监督成分构建初始的社团结构框架,然后充分利用它们以贪心方式对每一社团进行扩张,得到最终的社团结构。为了测试、验证这三种方法的性能,本文分别在一些实际网络数据集上进行了实验。实验结果证实,这三种方法均具有较强的社团检测能力,得到的社团结构质量明显优于对比方法。第二类方法的目标是从网络中高效地获取基本合理的、确定的社团结构,以克服一些运行效率较高的社团检测方法得到的结果具有不确定性的缺陷,并增强社团检测方法的泛化能力,方便对未知的新网络快速地进行探索性挖掘。主要包括两种社团检测方法:(1)VSAHCD:该方法受人类社交活动中选举投票行为的启发,首先通过模拟投票过程,让每个顶点按照一定的规则进行投票,得到一系列的小团体,然后分别使用两种策略,将其中一些小团体合并为较大的社团。一种策略借鉴了Fast算法的思想,每次合并能使得模块度增量最大并且相似性不为0的两个社团;另一种策略则合并相似性最大的两个社团,但确保合并操作能带来正的模块度增量。通过分别以这两种方式对小团体进行合并,得到最终的社团结构。(2)LPAd:该算法是对LPA算法的一个改进和增强,首先确定了一个合理的顶点序列,按照该序列的顺序,将其中每一顶点的标签更新为其邻居中最频繁出现的一个标签,同时也提出了存在标签竞争时的解决方案。通过这两方面的改进,使LPAd成为一个确定性的算法。然后在其运行得到的社团结构基础上,借鉴Fast算法的思想并结合相似性对其中一些社团进行合并,得到最终的社团结构。理论分析表明这两种方法均具有较高的运行效率。此外,本文也通过在5个实际网络数据集和2个LFR人工合成网络数据集上的实验,分别对这两种方法的性能进行了测试和评估。评估结果表明,这两种方法均能快速地从网络中检测得到比较合理的、确定的社团结构。

关键词： 社会网络   社团检测   层次结构   随机游走   线性规划  

摘要： 社团结构是分析社会网络的重要结构之一,其内部成员在社团中起着不同的作用。在多种分辨率下,社团的规模也有所不同。当前的社团分析方法只检测给定性质的成员,因此只能检测到固定数量的成员层次,并且成员层次与社团结构不一致。这些方法度量成员的归属程度之后,通过预先设定的阈值来得到多种分辨率下的社团结构。阈值的设定使其难以广泛应用于实际问题。为了解决这些问题,本文介绍一种新型的结构,称为社团成员层次结构。该结构根据成员归属于社团的程度将成员划分为多层,可以构建多种分辨率下的社团结构,反映社团成员的性质。本文给出社团成员层次结构的定义,并讨论其连续性,可比较性,一致性和稳定性。为了检测该结构,本文在基于种子的社团检测框架下,提出社团成员层次结构检测框架,并给出基于随机游走和线性规划的社团成员层次结构检测算法。此外,为了应对社会网络中经常出现的块结构和星型结构,本文提出基于边模式的种子社团检测算法来检测含有这两种结构的种子社团,并进行实验来分析验证。通过在多种规模的真实社会网络中进行定性实验和定量实验,本文分析了检测到的社团成员层次结构在真实社会网络中的意义,并分析了提出的算法在社团检测问题上的效率。最后,本文以两个应用问题为例,介绍利用社团成员层次结构解决实际问题的能力,包括大规模网络的可视化以及商品的交互式推荐。

关键词： 组织动态分析   组织异常检测   社团演化分析   异常子序列  

摘要： 组织是为完成特定目的形成的功能成员及其属性和关系的集合,现实中各种有形无形的组织影响着人们生活的方方面面,组织异常可能预示着组织的重大行动,可能指示组织演化模式的转变,或者蕴含其他有趣的知识。对这些知识的挖掘有助于我们更好的认识组织演化的过程,甚至预测组织发展的方向。本文基于组织网络序列,重点从组织社团演化的角度描述组织动态,形成了组织社团划分、社团演化分析和异常子序列检测三方面的研究成果。论文的主要创新点如下:(1)提出了一种基于F检验的社团合理数量评价指标。本文采用对节点特征向量聚类的方法进行组织社团划分,而聚类方法面临的主要问题是如何聚类数量。受统计学中方差分析方法的启发,本文提出了针对社团划分的F统计量,用于评价划分各社团的差异程度,作为社团数量的估计指标。通过对社团划分的基准网络和两个现实网络的实验,验证了基于F统计量的社团数量评估方法是有效的,并且基于EM算法实现的社团模糊社团划分方法也取得了很好的表现。(2)提出了一种基于社团角色熵的社团演化指标和一种网络相似度的实现形式。本文利用组织网络节点的局部聚类系数描述节点的角色,并利用信息熵的思想构造社团角色熵,社团角色熵反映了组织成员角色在社团中分布的异质性。组织网络相似度是衡量组织结构变化程度的常用度量指标,本文总结分析了现有的四种相似度指标,并提出了一种基于网络余弦相似度的指标。最后在组织动态描述实验中验证社团角色熵指标和网络相似度指标的有效性。(3)提出了一种基于邻域一致性的异常子序列检测方法。本文定义了子序列和邻域子序列的概念,利用多元线性回归模型描述邻域子序列重构的过程。并利用回归系数(重构权值)和重构偏差定义了一致因子,指标描述子序列与其邻域的一致性,而且提供了基于最小二乘估计和偏差优化两种方法计算一致因子。实验发现一致因子能够从含义较为模糊的组织动态序列中分辨组织演化的不同阶段和异常子序列,还提供了参数的选取的参考方法。

关键词： 数据挖掘   复杂网络   社团检测   影响传播  

摘要： 复杂网络具有多种特性,社团结构被认为是复杂网络最重要的一个性质。社团结构简单的说就是网络中一组节点的集合,在同一个社团内部的节点之间的关系紧密,而社团与社团之间的关系与之相比则十分稀疏。社团结构与网络中某些特定的功能及性质有着密切的联系,因此检测网络中的社团结构对于分析和理解这些复杂网络系统起着至关重要的作用。本文主要针对复杂网络中社团检测问题进行研究,主要研究内容有:首先,在社团结构形成过程中,起初往往是由有少数用户发起建立从而逐渐发展成为社团,而初始的这小部分用户可以看作是社团内的核心用户。本文根据社团演变的过程提出了基于核心节点的社团检测算法,主要分为三个步骤:1.检测核心节点;2.发现核心社团;3.构造全局社团结构。在合成网络和真实网络中进行的实验表明了基于核心节点的社团检测算法的有效性。其次,考虑到当前网络规模不断增长,快速有效的社团检测方法显得尤为重要。本文利用到了节点自身属性这一因素,并且将网络的拓扑结构特征和节点自身属性结合到一起来检测网络中的社团结构,提出的基于属性传递的社团检测算法能够快速检测复杂网络中的社团结构。在真实网络数据中进行的实验能够反映算法的高效性。最后,本文从影响传播的角度来解决社团检测问题,我们首先讨论了二者之间的关系,然后提出了一种新的传播模型IC-A,该传播模型基于真实的动作日志,并且利用提出的模型的在网络中筛选种子节点,然后利用到了队列来快速的检测社团。在真实网络中进行的实验不仅表明了利用影响传播的方法来解决社团检测问题的可行性而且检测到的社团同样能够促进影响传播的进行。

关键词： 同步理论   股票网络   社团结构   社团检测  

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

关键词： 信任关系网络   社团结构   有向加权模型   节点相似度   评价函数  

摘要： 针对群智计算和感知服务中不可信服务节点可能引入的安全威胁问题,提出了一种基于节点间信任关系网络的社团结构检测算法。该算法通过分析信任关系网络的功能和结构特点,引入连接的方向和权值因素,建立有向加权网络模型,定义最优路径相似度作为节点聚合标准,提出社团离散指数作为评价函数控制检测过程,从而准确识别信任关系网络中的可信节点集合,为服务节点选择提供参考。算法引入节点相似度阈值和归属判定指数控制社团聚合,与误分类节点再筛选环节配合,有效降低了检测过程中的节点误判概率,有针对性地设计社团离散指数作为评价函数,动态评估检测结果并调节聚合参数,保证了社团结构检测结果的准确率及合理性。实验结果表明:该算法能够有效实现信任关系网络中社团结构的检测与识别,与已有算法相比,检测准确率提高了5.88%。

关键词： 社团检测   复杂网络   自然最近邻居   结构相似度  

摘要： 针对传统社团检测算法无法判断网络中特殊节点和SCAN算法对于参数依赖性太大的缺点,提出了一种基于自然最近邻居概念的社团检测算法CD3N。算法利用自然最近邻居无参的特性,首先以结构相似度为基准,计算出网络节点的自然最近邻居,并依此构造小值最近邻域图;然后取邻域图中邻居数最多的节点为核心节点,根据可达关系,构造关于核心节点的社团;重复选取核心节点并构造社团的过程,直到没有可归入社团的节点。将算法应用到空手道俱乐部网络和海豚网络中,并与SCAN算法进行对比。实验结果表明,CD3N算法有效解决了参数敏感性问题,能够很好地进行社团检测。

关键词： 社团检测   动态图   动态社会网络   模块度   时间序列  

摘要： 真实社会网络如邮件、科学合作、对等网络等均可以用图进行建模。近年来,基于图的社团挖掘吸引了人们越来越多的研究兴趣,它不仅可以帮助识别网络的整体结构,还可以发现社团演变的隐藏规律。尽管使用静态图进行社团挖掘已经被广泛采用,但基于动态图的研究还比较少。通过使用时间序列,对动态图上的社团挖掘包括社团检测与分析进行研究,提出了一个新的动态社团结构检测模型,并采用真实网络数据集进行了实验。实验结果显示该模型在社团结构发现的有效性和效率性方面均有着良好的表现。