关键词： 社交网络   社团抽取   社团检测   社团结构   网络搜索  

摘要： 针对现有的社团分析算法无法在大规模网络上应用的问题,提出一种社团抽取算法,可以高效地分析网络的社团特征.该方法无需事先获取网络的全部拓扑结构,采用网络搜索与社团判定相结合的思路,可有效地抽取结构未知的社交网络上的某个特定社团,从而使分析超大规模网络社团结构成为可能.在仿真数据集上进行实验,分析抽取准确率的影响因素,得出网络平均度越大抽取准确率越高.进一步实验结果表明,社团抽取算法的准确率与现有方法接近,并且执行效率明显高于现有方法,验证了该算法的可行性和有效性.

关键词： 复杂网络   社团结构   社团检测   结构相似度   仿射传播  

摘要： 复杂网络中普遍存在着一定的社团结构,社团检测具有重要的理论意义和实际价值。为了提高复杂网络中社团检测的性能,提出了一种基于结构相似度仿射传播的社团检测算法。首先,选取结构相似度作为节点之间的相似性度量,并采用了一种优化的方法来计算复杂网络的相似度矩阵;其次,将计算得到的相似度矩阵作为输入,采用快速仿射传播(FAP)算法进行聚类;最后,得到最终的社团结构。实验结果表明,所提算法在LFR(LancichinettiFortunato-Radicchi)模拟网络上的社团检测平均标准化互信息(NMI)值为65.1%,要高于标签传播算法(LPA)的45.3%以及CNM(Clauset-Newman-Moore)算法的49.8%;在真实网络上的社团检测平均模块度值为53.1%,要高于LPA算法的39.9%以及CNM算法的47.8%,具有更好的社团检测能力,能够发现更高质量的社团结构。

关键词： 手持设备网络   社团检测   数据转发  

摘要： 针对手持设备网络,提出动态分布式社团检测算法。首先利用节点相遇历史数据计算累积相遇持续时间与相遇次数均值,并作为动态阈值确定节点朋友集合,然后构建本地关系图,最后对本地关系图进行多社团检测。仿真结果表明该算法能够反映节点间关系的变化,更适用于动态变化的移动容迟网络环境。

关键词： 微博   话题检测   复杂网络   重叠社团发现  

摘要： 微博话题检测是当前研究的热点,提出一种基于复杂网络重叠社团发现的微博话题检测方法。该方法对一段时间内的微博数据进行预处理,在分词后,根据词性以及词的时域分布抽取出主题词,在相关度高的主题词之间构造边得到复杂网络。引入社团独立模块度的概念,并通过社团独立模块度最大化模型发现重叠社团,把每个社团看成一个微博话题。重叠社团发现的方法可以解决由一个或多个主题词属于多个话题引起的话题检测准确率低的问题。实验结果证明了该方法在微博话题检测中的有效性。

关键词： 复杂网络   社团检测   成对约束  

摘要： 网络中的社团结构检测问题已被广泛研究,但当网络中的噪音不断增加时,已有的社团结构检测方法的性能下降较快.为解决此问题,文中将成对约束形式的先验信息结合现有的社团结构检测方法,通过先验信息引导极值优化社团发现过程,提出基于网络结构极值优化的半监督社团划分方法.实验表明,相对已有方法,文中方法能提高社团划分准确度,且在噪音网络中也显示出较好性能.

关键词： 模式概化   社团检测   实例概化   原生实例   新生实例  

摘要： 随着数据库规模的日益扩大,数据库的模式也愈加复杂,再加上文档资料的缺乏,用户需要投入大量的时间来理解和操作数据库。现有的数据库概化方法只是对数据库中的模式进行概化,通过关系表中的主外键信息或者社团检测算法,制定相应的评价函数,挑选出数据库中相对重要的表,作为概化结果提供给用户。但是随着对数据库的深入研究,表中实例规模的突增,模式概化已经不能满足用户的需求。基于此,本文主要从两部分对数据库进行概化,第一部分是模式概化,通过改进现有的社团检测算法,在不需要事先确定社团个数的前提下,将联系紧密的表划分到同一个社团中,再为每个社团挑选出最重要的表,作为该类的标识。第二部分本文对数据库实例概化技术进行研究,在模式概化的基础上,为各个表挑选出重要的实例,并将概化结果分为原生实例和新生实例。原生实例主要基于文本挖掘技术和扇出值进行概化,利用文本挖掘技术提取特征项,并选取各表中权值较大的特征项作为部分概化结果；另外本文还引入扇出的概念,根据表在记录层上的连接关系,扇出值越大,说明该记录实例化连接边的能力就越强,该记录也就越重要,从而为用户挑选出重要的记录。新生实例的研究主要是基于文本短语相似度技术,通过对表中某一字段值进行聚类得到概化结果,本文还介绍了对数值型数据的概化方法,并且通过实验验证了文中方法的可行性,不仅可以通过模式概化为用户提取重要的模式,而且可以通过实例概化为用户挑选出特征实例,使得不熟悉数据库的用户能快速了解数据库的主题信息,便于日后检索和查询。

关键词： 复杂网络   社团检测   归属度   节点相异性   节点相似性  

摘要： 近年来,随着互联网和计算机技术的快速发展,以社会关系网络、生物信息网络、语义Web网络等为代表的复杂网络迅速兴起,复杂网络的相关研究也得到了学术界和工业界的广泛关注。社团是复杂网络的重要特性,代表着网络中具有一定关系对象的集合。社团内部的节点之间连接紧密,不同社团节点之间连接相对稀疏。通过对复杂网络中社团结构的研究,可以得出复杂网络的功能、拓扑结构和性质等信息,这对于了解网络结构,充分发挥网络价值都很重要。社团检测就是利用复杂网络中已知的节点属性信息、节点连接关系信息以及拓扑结构信息等来发现网络中特定群体的潜在规律,进而挖掘其潜在价值。当前大部分的社团检测算法都是基于网络拓扑结构展开的,这类算法普遍存在着准确率低、时间复杂度高及聚类因素单一等不足。标签传播算法是常见的基于网络拓扑的社团检测算法,具有快速、简单、高效的特点,但也存在随机性、准确性和鲁棒性的不足。针对上述问题,本文综合考虑节点属性信息以及图的拓扑结构信息,提出了两种新的改进的基于标签传播的社团检测算法。首先,基于节点归属度的标签传播社团检测算法。该算法首先从未被分类的节点中选择一个度数最大且聚类系数符合条件的节点及其邻居节点作为初始社团,然后根据节点归属度吸引它的邻居节点加入,形成大致社团结构,最后运用标签传播算法思想进行完善,得出最终的社团结构。基于节点归属度的标签传播社团检测算法适用于中小规模网络,时间复杂度低,且能够准确的检测出复杂网络中的社团结构。其次,针对上述方法在顶点数量多,边数密集的复杂网络中社团检测准确性不足的情况,提出了基于节点相异性的标签传播社团检测算法。该算法首先通过节点度数、节点聚类系数和节点相异性进行核心点集合选取,然后从核心点集合中选择核心点,根据节点相似性公式,将符合条件的邻居节点加入到相应社团,形成大致社团结构,最后根据多数投票原则修改节点标签,以获得最后准确的社团结构。基于节点相异性的标签传播社团检测算法充分考虑了各节点间的直接联系和间接联系,使社团的检测效果更加完善,准确性得到了进一步的提升。最后,针对上述社团检测方法,本文运用大量实验进行了验证。通过对检测出的社团结构的有效性和社团检测的执行效率进行测试,充分验证了本文社团检测方法的可行性和优越性。

关键词： 社团检测   层次凝聚   标签传播   半监督学习和主动学习  

摘要： 近年来,随着复杂网络数量的不断增多,复杂网络所涉及的领域不断扩大,对复杂网络性质的研究已经成为一门非常热门的课题。复杂网络通常具有一定的社团结构,即社团内部的关系紧密而社团与社团之间的关系稀疏,对应到网络图上就是社团内部的边多而社团与社团之间的边稀少。如何快速、有效地从复杂网络中获取社团结构,是大多学者研究的主要方向,也具有重要的应用价值。本文通过查阅相关的中外文献,对现有的社团检测算法进行研究,设计了两种新的社团发现算法：基于少量选点的层次凝聚社团检测算法(HCDFSN)和基于少量选点的主动半监督社团检测算法(ASCDFSN)。HCDFSN算法介绍了一种节点相似性度量方法、核心节点度量方法以及根据相似性处理社团间重叠节点的方法。该算法的大致思想为从核心节点出发来构建新的社团,直到所有核心节点用完为止；然后处理社团间重叠的部分；最后基于模块度对初始社团合并得到最终社团结构。HCDFSN算法通过初始社团形成方法和社团边界处理方法可以解决以下两个问题：(1)层次凝聚算法中社团边界节点一旦分错,不能重新划分问题；(2)层次凝聚算法中效果不理想问题。ASCDFSN算法介绍了一种得分计算方法、候选节点获取方法以及主动半监督策略。该算法的主要思想是通过得分计算方法获取候选点集合；再从候选节点中选取一部分节点,进行人工标记；最后使用半监督思想进行社团检测。ASCDFSN算法通过得分选取策略和主动半监督策略可以解决半监督算法中以下三个问题：(1)随机选取少量节点导致社团检测效果不佳问题；(2)选点经常不能覆盖所有社团问题。本文在多个真实网络数据集和一个人工合成网络数据集上进行实验,对算法运行的过程进行可视化展示。并通过与同类型算法的实验结果对比和复杂度分析表明,HCDFSN算法和ASCDFSN算法在社团检测上有较好的效果且效率较高。

关键词： 复杂网络   引力场   建模   社团检测   链接预测  

摘要： 复杂网络可以揭示复杂真实系统的许多相关特征,如结构、功能及二者的相互作用,近年来吸引了来自物理、生物、社会和工程等领域研究人员的广泛关注,然而当前大多数研究却很少从物理学的角度来建模进而提出问题的解决方法。本文将网络中的节点看作是空间的一个质点,每个节点均对其它节点产生某种“作用力”,通过研究由该网络的组成元素所形成的虚拟引力场,进而从另一种角度解决当前复杂网路研究的一些重要课题。 本文首先从物理力学角度出发,通过赋予网络节点一些物理属性如质量、距离等进而将复杂网络看作是虚拟空间中的力学系统,经一系列理论和方法计算网络节点间的虚拟引力及由引力导致的网络内部关系的变化,从而对复杂网络抽象图表示的引力场进行建模。网络的引力场体现了数据间的自然吸引属性,可以经过相关参数的选择满足处理不同网络在数据挖掘及其它领域问题的需要。 其次,针对现有解决网络社团挖掘问题的方法大多基于优选法或试探法导致的收敛速度较慢且划分准确率不理想的缺陷,我们根据复杂网络引力场中的虚拟引力定义和分析了基于该模型的社团结构概念以及内在特性,并基于此概念提出了一个用来分析和挖掘网络社团的迭代方法NC-DF(Network Communities in Data Field)。该方法充分利用节点引力所表现的抱团特性,能够完全自适应地执行,无须预先设置参数。和常用的几种社团检测方法相比,NC-DF算法在迭代过程中能够快速收敛使社团划分结果达到稳定,并且在仿真网络和真实网络上均有较好的表现。 最后,针对现有链接预测方法大部分都只是基于节点的共同邻居的个体信息来考虑相似性,对共同邻居节点间相互作用考虑不足这一缺陷,根据网络的引力场模型中任一对节点间存在的吸引力提出了一种新的相似性计算方法—共同邻居团的吸引密度AD (Attractive Density)。该方法充分利用了网络的结构信息,使用共同邻居团内的吸引密度来衡量每对节点的相似性大小,既考虑到单个邻居节点的作用,又充分利用了共同邻居节点间的相互作用关系。AD方法在保证时间效率的情况下具有更好的预测结果,特别是在聚集系数较低的网络上较好地改善了预测的性能。

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

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