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

摘要： 现实世界中众多的复杂系统都可抽象地表示为复杂网络,而社团结构是很多复杂网络最为显著的结构特征,其中的社团往往对应于网络的功能单元,从某种程度而言,整个网络的功能往往取决于社团之间的相互作用。通过检测网络的社团结构,可以在中观(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人工合成网络数据集上的实验,分别对这两种方法的性能进行了测试和评估。评估结果表明,这两种方法均能快速地从网络中检测得到比较合理的、确定的社团结构。

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

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

关键词： 动态网络   局部优先   标签传播   重叠社团   非重叠社团  

摘要： 复杂网络能够刻画现实世界中的大量现象,对复杂网络的研究受到了人们越来越多的关注。在现实世界中,复杂网络的结构并不是一成不变的,而是随着时间的变化而不断改变,从而形成了动态网络。动态网络对于刻画随时间变化的自然和社会现象具有极大的潜力,对动态网络的研究具有很强的现实意义。传统的动态网络社团发现算法往往分别对每一个时刻的网络快照进行聚类,然后分析相邻时刻社团之间的演化关系。这种方法的缺点之一就是没有考虑动态网络的时序特点,聚类仅仅基于单一时刻网络的结构,难以刻画社团的演化特性。基于这一观察,本文提出了一种局部优先的演化聚类方法LEOD以及一种基于标签传播的演化聚类算法DLPAE。对于LEOD,它针对某个时间点的快照网络,以网络中的每个结点为中心,首先在该节点的邻居网络上通过标签传播算法检测得到Ego社团。然后将这些局部Ego社团不断合并,从而得到网络的全局社团结构。在执行社团合并的过程中,通过引入社团相似度和关联度两个概念,并利用演化聚类框架,实现了局部优先的动态网络社团检测与演化分析。在DLPAE中,节点的社团标签由其邻居节点投票决定,且每个邻居节点对该结点都具有各自的影响力,我们称之为置信度。在聚类的过程中,节点的置信度的计算不仅要考虑当前时刻的网络结构,同时需要考虑前一时刻网络的结构,从而保证了聚类的时序特性。同时,对于每一个节点,DLPAE计算其节点的置信度方差,并按照节点置信度方差从大到小的顺序更新节点的标签,从而提高社团检测结果的稳定性与准确率。在DLPAE中,每个节点可以持有一个或者多个社团标签,该属性使得DLPAE能够同时发现动态网络中的重叠社团与非重叠社团。本文在真实和人工数据集上进行了大量的实验来评估本文提出算法的性能。实验结果表明,LEOD能够有效地检测出动态网络中的重叠社团结构,发现网络中潜在的信息;而DLPAE能够同时检测网络中的重叠社团和非重叠社团;和同类算法相比,本文提出的算法表现出了较好的性能。

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

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

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

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

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

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

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

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

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

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

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

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

关键词： 聚类划分   社交网络   重叠社团   k-均值   随机游走  

摘要： 大数据环境下社交网络的社团结构研究对解决很多现实问题有着重要的意义。社团通常被看作是有相对紧密的内部连接和比较稀疏的外部连接的子图,重叠是社团结构的一个重要特征。论文基于G(n,p)模型,提出了一种生成包含重叠社团的合成网络的方法,然后基于k-均值和随机游走设计了一种重叠社团的检测算法,并在合成网络上初步验证了该方法的可行性。