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

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

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

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

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

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

摘要： In a very general context, communities in networks are defined as groups of nodes that have some common properties such that connections are stronger between the nodes in a community than with the nodes in the rest of the network. It is quite common for nodes to participate in multiple communities. Therefore a community detection algorithm for such applications should be able to detect overlapping communities. However, overlapping community detection is more computationally intensive than disjoint community detection and presents new challenges that algorithm designers have to face. Besides, the big data phenomenon with exabytes of data brings up datasets that take too long to analyze using even the fastest algorithms currently available. Fortunately, the amount of computing power available to researches also increases. This computing power usually comes structured as a number of cores, processors, or machines joined together to form a high performance computer, cluster or a supercomputer. In this thesis we analyze what other researchers have done to utilize high performance computing to perform efficient community detection in social, biological, and other networks. We use the Speaker-listener Label Propagation Algorithm (SLPA) as the basis for our parallel overlapping community detection implementation. SLPA provides near linear time community detection and is well suited for parallelization. We explore the benefits of a multithreaded programming paradigm for both synthetic and real-world networks and show that it yields a significant performance gain over sequential execution in detecting overlapping communities.

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

摘要： 随着社会的发展,越来越多的复杂系统和社交网站开始流行。复杂系统和社交网络可以被抽象地描述为复杂网络,如常见的朋友关系社会网络、科研合作网络、电影演员合作关系网络、交通运输网络等等。与此同时,社团结构作为复杂网络的一个关键结构规律吸引了越来越多的科研人员对其进行研究。因此,如何准确检测出复杂网络中的社团结构也成为了一个重要的研究课题。 本论文主要研究社团检测问题。针对部分社团检测算法在社团结构不明显的情况下并没有较好的检测结果,本文提出了两个社团检测算法：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)提出了一种非对称相似性度量,基于该度量构建了一个快速主动半监督社团检测算法。提出的非对称相似性度量方法能够更好地度量网络中相邻节点之间的相似性。提出的主动半监督社团检测算法部分地将社团检测过程融入到了节点的主动选取过程中,大大降低了半监督社团检测算法的时间复杂度。

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

摘要： 很多自然和社会中的复杂系统，都可以按一定的方式描述成图或者网络。这些网络具有复杂的内部结构，因此称为复杂网络。近些年来，随着复杂网络在众多领域中的广泛应用，复杂网络中的社团检测与分析也越发受到人们的注意。社团结构的特点在于社团中的节点处于一种高密度的集聚状态而社团之间的节点则处于一种低密度的连接状态，而社团检测最基本的作用是将个体进行社团分类，将个体分配到若干社团中。该问题的深入研究有助于以一种分而治之的方式研究整个网络的模块、功能及其演化，更准确地理解复杂系统的组织原则、拓扑结构与动力学特性。 到目前为止，人们提出了许多算法来检测复杂网络中的社团结构。典型的社团检测算法大致可以分为传统的分级聚类和图形分割算法，比如Kemighan-Lin算法和谱平分算法，以及GN算法和Newman快速算法。这些算法都有各自的优势和不足，都有其特定的适用范围，还需要进一步改进。如有的算法在计算效率方面，有的算法在算法思想方面仍值得改进。但是，这些算法绝大多数都是将网络检测成为若干个相互分离的社团，准确度在一定程度上取决于初始条件的选择，并且不能识别网络中的一些重要节点。2011年Xu Xiaowei提出了一种基于结构相似的社团结构检测算法SCAN。该算法的优点是不仅可以对网络进行社团结构的检测，并且可以找出网络中的特殊节点。但该算法的不足在于对参数的选择非常敏感，难以保证检测出的社团的质量。 本文在SCAN算法的启发下，借用结构相似度的思想，利用自然最近邻居算法无需参数的优势，提出了一种新的社团检测算法——基于自然最近邻居的社团检测算法CD3N。同时，邻居本身就包含一种社团的概念，这使得自然最近邻居算法可以很好的理清复杂网络中的节点关系。本文对原有的自然最近邻居概念进行了改进，使用结构相似度代替距离作为邻居的判定依据，详细分析了各种自然最近邻域图的优缺点并提出了一种适用于社团检测的自然最近邻域图的构造方法。最后使用真实数据集进行实验，与源数据划分结果和SCAN算法结果进行对比分析，证明了算法的可行性和有效性。

关键词： 动态网络   社团检测   局部模块度   重叠性   层次性  

摘要： 随时间缓慢变化的复杂系统可以建模为抽象的动态网络。由于动态网络在社会学、生物信息学、物理、计算机等研究领域有广泛应用,越来越受到科研工作者的重视。近几年动态网络成为科研热门领域,具有实际意义的动态社团结构是动态网络中普遍而又重要的特征。当前动态社团检测算法仍主要基于静态检测方法的相关理论基础。基于极大化Q函数的动态社团检测算法存在分辨率问题,即为了获得更优的模块度值小社团常被合并为大社团。另一方面,很多动态社团检测算法需要设置多个参数或阈值,这就要求对网络有一定的先验知识或需要借助Q函数对结果进行判定。而且,已有的动态社团检测算法不能识别出如社团间的重叠结构等重要拓扑特征。为解决上述问题,本文提出了一种基于进化聚类和局部模块度的重叠结构动态社团检测算法。基于局部模块度的社团检测方法,将整个网络的社团检测问题转化为自底向上的凝聚问题,能适应网络中规模不等、密度不均的社团结构。通过统计节点随机游走行为特征,增强无权网络的分辨率,并使用进化聚类框架下的时序开销嵌入技术来平衡当前社团的拓扑特征与历史信息,从而检测出社团演化的动态规律。该算法仅在进化聚类过程中对平衡因子进行设置,无需领域先验知识。本文使用真实网络数据对该动态网络社团检测算法进行评估,包括Drosophila melanogaster数据集和科学家合作网络(DBLP)数据集。实验结果表明,基于进化聚类框架和局部模块度的动态社团检测算法与基于进化和局部优先的算法相比,扩展模块性指标提高了15%,显著提高了Drosophila melanogaster社团检测结果质量。并且,该算法能有效刻画出DBLP中科研团队的动态演化过程。综上,该算法可适用于无社团结构先验知识的网络,有效检测出具有特定意义的小规模社团及其重叠结构。