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

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

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

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

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

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

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

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

关键词： 网络社团检测   客户细分   节点中心性   随机漫步模型算法   电信  

摘要： 现有的电信客户细分方法无法发现基于个体间交互关系形成的客户群体。为此,提出基于网络社团检测的电信客户细分模型。考虑网络加权方法对社团检测效果的影响,采用电信企业的通话明细记录构建不同的加权电话呼叫网络,并采用随机漫步模型算法建立基于通话关系的客户细分模型。在细分模型的基础上,结合客户基本信息分析社团的特征,使用网络节点度中心性识别社团中的中心客户。经电信运营商客户通话数据的分析表明,以通话总时长进行加权的网络得到的社团检测效果最佳,可以用于检测客户的关系圈,发现具有领导地位的中心客户,为电信企业客户挽留、精准营销等提供有效的决策支持。

关键词： 移动容迟网络   社团检测   数据共享   源路南中图法  

摘要： 针对移动容迟网络中的数据共享服务,提出基于社团的源路由算法(Social-based Source Routing,SSR)。将移动容迟网络中的数据共享过程分为摘要消息广播、兴趣消息回传与内容数据转发。利用分布式社团检测算法区别各节点的多社团结构,通过摘要消息广播构建节点间的社团路径(Community Path),并将共享数据沿社团路径进行基于单消息副本的转发。仿真结果表明算法在一定条件下能够达到与多副本转发算法类似的消息传输成功率,同时显著降低消息传输代价。

关键词： 社团检测   社团结构   节点度之差   节点相似性   最短路径  

摘要： 随着社会的发展,越来越多的复杂系统和社交网站开始流行。复杂系统和社交网络可以被抽象地描述为复杂网络,如常见的朋友关系社会网络、科研合作网络、电影演员合作关系网络、交通运输网络等等。与此同时,社团结构作为复杂网络的一个关键结构规律吸引了越来越多的科研人员对其进行研究。因此,如何准确检测出复杂网络中的社团结构也成为了一个重要的研究课题。 本论文主要研究社团检测问题。针对部分社团检测算法在社团结构不明显的情况下并没有较好的检测结果,本文提出了两个社团检测算法：DDSCDA和SPDDA。DDSCDA是基于节点度之差和节点相似性度量的社团检测算法,该算法首先从未分类的节点中选出一个度较大的节点作为核心节点吸引其邻居节点加入该社团,重复这一过程,直到所有节点都被划分到相应的社团；然后以得到的社团结构为起点,使用LPA算法的思想进行标签传播,直到每个节点的标签都与其邻居节点中占多数的标签一致。DDSCDA能够在预先不知道社团结构数目条件下,对社团结构不明显的网络能够准确的检测出其所包含的社团。 SPDDA是基于最短路径和节点度之差的社团检测算法。算法首先基于节点之间的最短路径和节点度之差进行候选核心点的选择,然后从候选核心点集合中选取未分类的核心点来吸引其邻居节点加入其社团,直到候选核心点集合中的元素都被遍历完时,得到最初的社团结构；然后根据多数投票原则对初始的社团结构进行修正得到最终的社团结构。此算法能够准确的检测出网络中所包含的社团结构。 论文在三个真实网络数据集和一个人工合成网络数据集上进行实验,并对算法的社团检测结果进行可视化显示。同时将提出的两种算法分别与LPA算法、LPAm算法以及FastQ算法进行比较。实验结果表明,两种算法都能够在无需预先知道社团数目的基础上,无论网络的社团结构是否明显,都能够准确的检测出所包含的社团结构。

关键词： 复杂网络   二分网络   社团结构   重叠节点   模块度  

摘要： 随着对复杂网络的物理结构和功能特征的深入研究,研究者们发现许多复杂网络都具有社团结构的特征。近年来,社团结构检测方法研究已成为复杂网络中热点研究问题之一。研究发现复杂网络中社团之间又存在重叠现象,且复杂网络中节点类型又具有二分特性。但是,目前常见的单分网络社团结构检测算法往往存在着复杂度较高、准确率较低或者无法检测重叠社团结构等问题；现有二分网络社团结构检测算法通常是将二分网络投影为单分网络,投影过程中会造成信息丢失等问题。为此,本文对单分网络和二分网络的重叠社团结构检测进行了深入研究,主要工作及创新点如下： (1)提出了一种基于核心节点和亲密度的重叠社团结构检测算法。 利用单分网络中节点类型唯一的特性,且存在着度值较大的节点,该算法率先引入核心节点概念。根据核心节点的特征从单分网络中抽取出核心节点,通过计算亲密度函数逐渐扩大核心节点这些初始社团,最终实现在单分网络中进行重叠社团结构检测。实验结果表明,该算法能够在较低的运行时间内完成重叠社团结构检测工作；根据模块度函数可获得准确度较高的重叠社团结构,符合现实复杂网络的实际社团结构特征。 (2)提出了一种基于扩展模块度的重叠社团结构检测算法。 由于传统层次聚类算法和分裂算法都具有较高的时间复杂度,又根据有权网络的结构特征,该算法首先提出了基于节点度值的种子社团概念,并给出了基于节点度值的种子社团所具有的特点。为了判断种子社团与其邻居节点之间的连接程度,又提出了吸收度函数。该算法的主要步骤是从单分网络中抽取出种子社团,再根据吸收度函数逐步扩大种子社团,从而得到基于节点度值的重叠社团结构。该算法分别在计算机生成网络和几个现实网络中进行了测试实验,实验结果表明该算法能够较准确地检测到重叠社团结构；将该算法与现有几种算法进了计算性能的比较,表明了该算法能够在大型复杂网络中较准确地检测出重叠社团结构。 (3)提出了一种基于极大完全子图的重叠社团结构检测算法。 根据现实复杂网络中可能包含大量极大完全子图、且又局部具有星型耦合网络结构特征,提出了一种基于极大完全子图的重叠社团结构检测算法。该算法首先通过深度与宽度搜索方法从单分网络中抽取到极大完全子图,再根据给定规则合并相邻的极大完全子图,最后通过扩展模块度函数判断社团结构检测结果。实验结果表明,该算法可以在较短的运行时间内保证重叠社团结构检测的准确性；同时也能够检测出重叠节点、链桥节点和孤立节点等具有特殊结构特征和功能特性的节点。 (4)提出了一种基于极大完全二分子图和二分聚类系数的重叠二分社团结构检测算法。 在二分网络中含有两种不同类型的节点,且连边只存在于异类节点之间。利用某种投影方法可以将二分网络投影为单分网络,但鉴于投影过程中都会造成某些信息丢失、边数剧增以及产生冗余信息等问题,提出了一种直接在原始二分网络中进行二分社团结构检测的算法。算法首先给出极大完全二分子图和二分聚类系数等相关概念。本算法包括两个主要步骤：1)根据极大完全二分子图的结构特征从二分网络中抽取出极大完全二分子图；2)根据二分聚类系数函数阈值合并相邻的极大完全二分子图。实验结果表明,当二分模块度函数处于某个极大值点的时候,该算法可以准确地检测到原始二分网络的重叠二分社团结构。 本文针对单分网络重叠社团结构检测提出的三种算法适用范围各不相同。其中,基于核心节点和亲密度的重叠社团结构检测算法适用于对含有度值较大节点的单分网络进行重叠社团结构检测；基于扩展模块度的重叠社团结构检测算法适用于对有权单分网络进行重叠社团结构检测；当单分网络中含有大量极大完全子图、且又局部具有星型耦合网络结构特征,采用基于极大完全子图的重叠社团结构检测算法进行重叠社团结构检测效率更高。 本文得到国家自然科学基金(61370145,61173183,60973152),高等学校博士点专项科研基金(20070141014),辽宁省高等学校优秀人才支持计划资助(LR2012003),辽宁省自然科学基金(20082165),中央高校基本科研基金(DUT12JB06)的联合资助。

关键词： 半监督聚类   K最近邻   主动学习   社团检测   标签传播  

摘要： 基于标签数据的半监督聚类利用标签数据提供的信息对聚类过程进行指导,以提高聚类算法的性能。如果标签数据的数量很少,则其分布很有可能无法覆盖到数据集中所有的类,亦即数据集中可能存在某些类,这些类不包含任何的标签数据,现有的半监督聚类算法将强制性地将这些类中的数据划分到其它的类中。当涉及到多密度不平衡数据集时,如使用随机方法选取标签数据,且只有少量的数据点被选取为标签数据的情况下,上述问题将尤为突出。 针对以上问题,本论文将对极少量标签数据下的半监督聚类进行研究,同时研究多密度不平衡数据集上的标签数据的主动选取策略,以所选的标签数据为基础构建半监督聚类算法,并将其应用于复杂网络社团结构的检测、分析之中。社团结构是复杂网络的最重要的特性之一,提取网络的社团结构具有非常重要的实际意义,因此社团检测已经成为统计物理、计算机科学、生物信息学等学科的一个重要的研究方向。 本论文的主要研究成果如下： (1)提出了一种基于极少量标签数据的半监督K均值聚类算法。该方法利用标签数据计算同一个类中的数据之间的相似性阈值,如果无标签数据与已有类中心距离的最小值大于该阈值,则增加一个聚类中心,重复这一过程,直到数据集中所有的数据到已有中心的距离的最小值都不大于该阈值。由于数据的相似性阈值是根据有限的标签数据获得的,这样获得的聚类中心的数目要比数据集中实际类的数目多,因此K均值聚类结果中类数目要比实际类的数目多。本论文提出了一种称之为类间影响因子的概念来度量类之间的相似性,根据类之间的影响因子的值对聚类结果中相应的类进行合并,最终得到一个聚类精度较高的半监督K均值聚类算法。 (2)提出了一种基于少量标签数据和标签传播的半监督聚类算法。该方法首先通过将标签数据的类别标签传递给其K个最近邻的方式扩展标签数据集；扩展过程结束后,如果剩余的无标签核心对象与已有类的距离大于指定的阈值,则增加一个新类,然后对该类进行扩充,扩充过程结束后再对新类进行检测,重复这一过程直到剩余的无标签数据中的核心对象与已有类之间的距离都小于指定的阈值。 (3)针对多密度不平衡数据集提出了一种主动半监督聚类算法。该方法首先利用最小生成树聚类方法将数据集划分为不相交的子集,在每个子集上选取密度最大的一个数据点交由领域专家进行标注,使其成为标签数据；然后按照标签数据的类别标签再将最小生成树的聚类结果进行合并形成初始的聚类结果；最后在每个类内根据类内数据的密度对标签数据集进行扩展,扩展结束后再利用K最近邻规则处理剩余的无标签数据。 (4)提出了一种基于标签传播的主动半监督社团检测算法。首先根据节点密度找出所有的核心节点,利用加权最短路径方法主动从网络的核心节点中进行节点选取,使选取的节点能够尽可能地分布到网络中所有的社团；然后将选取的节点作为标签节点,基于标签传播阈值(算法根据标签节点自己的特征自动获取该阈值)逐步将标签节点的社团标签传播到其邻居；最后使用修改的LPA(LabelPropagation Algorithm)算法对网络中剩余的无标签节点赋予一个社团标签。 (5)提出了一种非对称相似性度量,基于该度量构建了一个快速主动半监督社团检测算法。提出的非对称相似性度量方法能够更好地度量网络中相邻节点之间的相似性。提出的主动半监督社团检测算法部分地将社团检测过程融入到了节点的主动选取过程中,大大降低了半监督社团检测算法的时间复杂度。

关键词： 复杂网络   社团检测   密母算法   紧密度   模拟退火  

摘要： 现实世界中的很多复杂系统可以由网络表示出来,如技术网络、社交网络、交通运输网络及生物网络等。这些网络经过建模以后可抽象化为图,其中节点表示对象,节点之间的连接可以表示对象之间具有某种关系。社团结构是复杂网络的一个重要特性,它可以定义为网络中的一个由若干节点构成的子集,其内部节点之间连接紧密,而与网络中其他节点之间的连接较为稀疏。研究社团结构对于分析复杂网络的拓扑结构、理解复杂网络的功能、预测复杂网络的行为具有重要的意义。近年来,社团检测问题受到了各个领域的学者的广泛关注,许多算法也相继被提出来,如图划分方法、层次聚类法、谱聚类法、基于相似度的方法以及基于进化的优化算法等。密母算法是计算机科学和社会生物学的交叉产物,它建立在模拟文化进化基础之上,实质是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体。经过多年发展,密母算法已被越来越多的研究人员接受并广泛应用到组合优化、模式识别、图像处理等领域中。本文针对复杂网络社团检测进行了系统地研究,所取得的主要研究成果为:1.研究进化算法的基本理论,并深入理解密母算法及其改进算法在复杂网络社团检测问题中的应用。在此基础上,提出了一种利用局部结构信息的密母算法(Memetic algorithm using local structural information,MA-LSI)用于解决复杂网络的社团检测问题。在该算法中,利用模块度函数Q作为适应度函数,并利用一个局部社团的质量评价函数来定义局部搜索算子,此外还采用了一种节点移动策略来改善划分结果。与经典的快速纽曼(Fast Newman,FN)聚类算法和其他密母算法相比,实验结果表明该算法可以产生更为精确的划分结果。2.研究了传统的模块度优化所具有的分辨率限制问题,采用另外一个可以克服分辨率限制问题的目标函数:扩展模块度密度函数。该函数中含有一个可调参数,通过改变参数的取值可以实现以不同分辨率分析网络,从而检测出网络的多分辨结构。基于扩展模块度密度函数的优化,提出另外一种密母算法(Memetic algorithm with simulated annealing strategy and tightness greedy optimization,MA-SAT)用于复杂网络社团检测。该算法中有两个局部搜索算子,一个采用了模拟退火策略,另一个采用了局部社团紧密度函数的贪心优化。模拟退火策略可以加速算法的收敛且有助于算法跳出局部最优,紧密度贪心优化充分利用了网络的结构信息来产生邻居划分,计算代价小并且有助于提高种群的多样性。与几种经典算法对比的实验结果表明该算法是非常有效的。本文工作得到如下基金资助:国家自然科学基金(No.61003199),中央高校基本科研业务费专项资金资助(***140216和K5051202019)。