关键词： 社团检测   复杂网络   频繁项集   社团结构   标签传递算法  

摘要： 首先充分利用LPA的不确定性来构造事务数据,然后通过挖掘频繁项集的方法发现核心社团结构,对单个顶点构成的社团和核心社团进行合并,得到最终的社团结构.最后通过在5个实际网络上进行实验,实验结果表明,该方法在保持LPA算法高效率的情况下,能得到更好的、确定性的社团结构.

关键词： 共词分析   复杂网络   连边社团检测算法   科学计量学  

摘要： [目的/意义]传统共词分析的聚类算法存在以下不足:1关键词只能被划归一个聚类;2聚类过程对分类数目的确定缺乏严格判断标准。针对以上问题,采用复杂网络理论进行改进研究。[方法/过程]采用连边社团检测算法对关键词进行聚类,以科学计量学为例进行实证研究。[结果/结论]分析结果表明:算法对关键词的聚类结果有较好的改进效果,能够把核心度高的关键词同时划分到不同的研究主题之中,克服传统聚类算法的不足,而且划分密度可为聚类数目的确定提供客观判断依据。

关键词： 社团检测   局部信息   影响力节点   识别性能  

摘要： 针对规模化网络中局部社团检测存在的对初始节点位置敏感、拓扑信息难以有效利用问题,提出了一种采用影响力节点集扩展的社团检测(IN-LCD)方法。首先定义了节点的局部影响力指标,通过该指标计算并构造了源节点附近的影响力节点子集,然后从影响力节点子集开始,以迭代更新的方式,进行连续的社团扩张,最后通过节点和社团相似性指标计算,完成整个局部社团的获取。IN-LCD方法从有效利用节点局部信息出发,通过最具影响力节点集合进行社团扩展,有效克服了局部社团检测对初始节点位置敏感的问题。在真实和人工网络数据集上的实验表明,IN-LCD方法与已有的最佳局部社团检测方法相比,识别性能提升了5.3%,更能有效应用于局部信息出发的社团检测场景。

关键词： 半监督   动态   社团检测   非负矩阵分解  

摘要： 如何有效融合不同时刻的网络结构信息,是影响复杂网络中动态社团检测算法检测性能的关键和难点。基于此,提出了一种基于非负矩阵分解的半监督动态社团检测方法 SDCD-NMF,该方法首先有效提取了历史时刻所包含的稳定结构单元,然后将其作为正则化监督项,指导当前时刻的网络社团检测。在真实网络数据集上的实验表明,所提方法与已有方法相比具备更高的社团划分质量,更有利于探索网络的演变与发展规律。

关键词： 时变网络   社团检测   影响力节点识别   随机块模型   节点特性   Kerninghan-Lin算法  

摘要： 复杂网络社团检测有助于分析网络的结构和功能,是复杂网络研究的一项重要任务,近年来获得了广泛关注。另外,研究网络的影响力节点对于探索分析网络具有重要意义,相关研究工作已取得了一定成果。然而,目前大多数社团检测和影响力节点识别方法均只适用于静态网络而忽视了时序信息,因而无法较好的建模真实世界数据。针对上述问题,本文的主要研究内容如下:一方面,本文提出一种基于度修正随机块模型的时变网络社团检测方法。基于演化聚类框架,结合社团隶属矩阵将一个正则项引入到度修正随机块模型的目标函数中,并提出一种类似KL算法的模型求解方法。同时,利用网络交叉验证方法进行模型选择,能够处理社团个数随时间变化的时变网络,从而克服了一些动态社团检测方法假定社团个数是一个常量的问题。基于时变复杂网络的数据实验结果表明,与经典的动态随机块模型和FacetNet等方法相比,该方法的实验结果具有较高的准确性和较低的误差率。另一方面,为分析网络中的重要节点,将社团检测方法应用到时变网络影响力节点的识别问题中。通过识别演化社团中的影响力节点来识别整个识别网络的影响力节点。首先,基于度修正随机块模型获得各网络快照的社团结构;然后获取时变网络的各个社团的演化关系,为此,本文提出扩展的Jaccard系数用于匹配各网络快照的社团;最后,获取影响力节点的初步识别结果并利用三种广泛应用的中心性度量指标进行聚合。实验结果表明,本文的方法能够准确识别时变网络的影响力节点,同时也发现一些已被复杂网络或社会科学证实的有趣现象。综上所述,本文基于度修正随机块模型提出了一种时变网络社团检测方法,并将其应用于真实网络。此外,将度修正随机块模型应用于时变网络的影响力节点识别问题中,对于分析真实世界复杂网络具有一定意义。

关键词： 社交网络   局部社团检测   谱聚类   种子扩张  

摘要： 在我们的生活中需要处理分析很多规模很大的数据集,我们将一个大数据集成为网络。社团是网络里面的一种重要的属性,因为它们往往可以代表这个网络,拥有网络的核心价值。而现实网络中的社团结构往往是重叠的,所以那些非重叠社团检测算法就不能很好的处理现实网络,而能够检测出重叠社团的算法才能更好的应用于现实网络。本文提出一个基于局部谱的种子扩张社团检测算法(Spectrum Based Clique Expansion,SCE),SCE算法在找出所有种子集的基础上,对每个种子集进行随机游走,得到可以表示此种子集邻接结构的局部谱空间。在这个局部谱空间中,我们将求解社团问题转化为线性规划来解最小一范数向量,从而近似地求出此种子集所属的局部社团。由于种子集扩张是独立的,所以可以得到重叠社团。实验表明,SCE算法在使用不同种子集以及社团评估函数时,算法都可以保持良好的性能,具体很强的稳定性。在与其他代表性的种子扩张社团检测算法(比如,GCE算法和DEMON算法)相比时,通过实验结果可以明显看出SCE算法的性能优于GCE算法和DEMON算法。经过现实网络数据集的实验证明,SCE算法可以用于现实网络的社团检测。

关键词： 复杂网络   重叠社团   局部扩充   朋友分组   朋友推荐  

摘要： 近年来,复杂网络的研究已成为各个领域的热点课题,对计算机科学、经济学和社会学等众多领域的发展都产生了深远的影响。检测社团结构是复杂网络研究中一项基础而又重要的工作,在分析网络拓扑结构、挖掘网络潜在功能以及预测网络行为中扮演了重要的角色。由于网络中的节点通常属于多个社团,导致社团之间相互重叠,因此现实世界的真实网络往往存在重叠的社团结构,研究重叠社团结构可以更全面地认识和分析真实网络。基于此,本文对复杂网络的重叠社团检测问题进行了研究,提出了一种基于单步添加团的重叠社团检测算法,同时在此研究基础上对在线社交网络朋友推荐算法进行了研究,提出了一种基于单步添加团的社交网络推荐算法。本文的主要研究工作如下：(1)本文提出了一种基于单步添加团的重叠社团检测算法。局部社团扩充是当前检测复杂网络重叠社团结构的主流解决方法之一,其主要思想是从单个节点出发,通过不断添加一个新的节点来获得最终的社团划分。现有的采用基于单个节点逐步加入社团的扩充算法没有充分考虑到新添加节点的局部信息,从而在一定程度上影响了社团检测的准确性。团作为网络中的一个完全连通子图,该子图中所有节点两两之间相互连接,由于这种强连接关系,在社团检测中,团中的节点属于同一社团的可能性更大。基于此,在局部社团扩充的基础上,本文提出基于单步添加团的重叠社团检测算法,该算法在局部扩充社团时采用单步添加团的策略,在扩充过程中,若判断出某节点应加入到当前社团,则把该节点所在的团加入到当前社团中。在计算机生成网络和真实网络数据集上的实验结果表明,与现有重叠社团检测算法相比,基于单步添加团的重叠社团检测算法可以更准确地检测出网络中的重叠社团结构,特别是在网络社团结构不明显时本算法仍然可以取得较高的精度值。同时,相比较于多数传统重叠社团检测算法,本文算法也具有较低的时间复杂度。(2)本文提出了一种基于单步添加团的社交网络推荐算法。朋友推荐作为一种经典的信息推荐问题,对其研究可以帮助在线社交网络里的用户整理并分类他们的朋友圈,给他们推荐潜在感兴趣的信息资源。在朋友推荐算法中,能否实现对朋友进行比较准确的自动分组决定了推荐算法的性能。基于单步添加团的重叠社团检测算法,本文提出了一种新的社交网络朋友推荐算法。该算法将朋友分组和朋友推荐结合起来,首先利用单步添加团的重叠社团算法对社交网络进行社团结构检测,从而实现社交网络中的用户自动分组,然后根据得到的朋友分组结果,利用相似度函数为用户搜索最佳的朋友,给用户提供既高效又准确的朋友推荐。在现实世界社交网络上的实验结果表明,与其他常用的推荐算法相比,本文提出的基于单步添加团的社交网络推荐算法不仅可以准确地对社交网络进行分组,同时可以给用户推荐最佳的需求信息,实现更有效的朋友推荐。

关键词： 大规模手机数据   通讯网络   社团检测  

摘要： 大规模手机通讯网络揭示社会运行规律,是复杂网络研究中最具研究意义的真实网络之一。本文运用社团检测算法对大规模手机通讯数据进行社会网络的实证研究,具体工作如下:1、揭示了某实际网络的通话/短信结构、通话/短信网络特征。通话网络结构包括内部通话、市外到市内通话、市内到市外通话的节点数和通话次数占比;短信网络结构包括内部短信、市外到市内短信、市内到市外短信的节点数和短信次数占比。通过从通话网络节点分布、边分布和相关性对比等网络结构和度分布、强度分布等网络特征研究方法来对大规模通话和短信网络进行实证研究。2、对比了三种算法处理大规模真实通话网络时在社团划分评价指标下的表现。基于并行非负矩阵分解的社团检测(CNMF)算法、基于节点链接关系随机游走的社团检测(InfoMap)算法和标签传播(LPA)算法对某实际网络的通话数据构建的MPC网络进行社团检测,并通过社团结构化评价指标:密度、聚类系数、传导性、三角形参与比例指标和统计学评价指标:准确率、召回率、Fmeasure、精确性和NMI对三种算法在处理大规模真实通话网络时的表现进行对比。3、对比了三种算法处理大规模真实通话网络时在多种网络特征下的表现。使用CNMF算法、InfoMap算法和LPA算法对MPC网络的社团划分结果进行社团大小、社团总度、社团最大度、社团密度、社团平均好友、社团中心节点重要性等网络特征的对比分析,对通话网络的社团结构进行实证研究。本文采用CNMF、InfoMap、LPA三个算法对实际网络进行社团划分的实证研究。三种算法对比:CNMF算法时间复杂度高,但是稳定、结构性强;InfoMap算法整体性强,运算速度快,聚类效果差;LPA算法被迭代调用,实现网络局部最优,指标计算效果好,但是整体性不强。

关键词： 社团检测   用户特征   谱聚类   本征间隙  

摘要： 随着Web2.0时代网络应用与移动终端设备的蓬勃发展,社会化媒体如雨后春笋般涌现,社会化媒体主张以用户为中心,鼓励用户创造内容。人们不仅将真实生活中的好友关系搬到了互联网上,还建立了不同于线下关系的线上虚拟朋友关系,如对名人、专业领域或娱乐公众号等添加关注,构建起全新的沟通与交流平台。当用户的好友规模日益壮大,发现沟通的效率反而大不如前,所有的朋友和公众账号每天发布的信息都会出现在用户的主页上,而用户主要关心的可能是某个朋友某方面主题的更新。过滤用户并不是真正关心的内容是社会化媒体必须解决的问题,这一问题的核心是如何正确真正地对用户的朋友圈进行分组。针对用户朋友圈分类模糊的问题,本文深入研究了社会化媒体的用户特征,得出两种在不同情形下适用的朋友圈检测算法:基于用户关系结构的社团检测算法和基于用户特征的社团检测算法。前一种算法适用于缺少用户基本特征的情形,从用户相互关注产生的关系拓扑结构入手,通过改进NJW多路谱聚类算法,使得算法可以对输入用户关系网络自动聚类。后一种算法适用于用户特征数据较完整的情形,综合考虑了用户基本特征和用户关系特征,并能根据用户个人网络的发展阶段,调节这两种特征相似性的比例。本文的主要研究成果为:(1)深入研究社会化媒体用户特征,将用户特征分为用户基本特征和用户行为特征,并对用户关系模型进行深入分析。本文还详细地阐述了通过爬虫技术来获取社会化媒体用户特征数据所遇到的两个技术难点。(2)基于用户关系结构的社团检测算法,对输入用户关系结构进行谱分析,由扰动理论中最大本征间隙所在位置与输入网络拓扑之间存在的关系,得到聚类数目,从而弥补了NJW多路谱聚类算法在确定聚类数目方面的不足,增强算法的自动性。(3)基于用户特征的社团检测算法,认为拥有共同好友数与相同特征背景的用户更易成为朋友,综合考虑了用户关系特征和用户基本特征,并能根据用户个人网络的发展阶段,调节两种特征的相似性的比例。最后,通过边聚类算法,将用户的个人网络进行聚类。

关键词： 加权网络   社团强弱度   局部社团检测   重叠社团检测  

摘要： 复杂网络普遍存在于现实世界中,对复杂网络的研究已经渗透到各个学科领域。社团结构是复杂网络最重要的特征之一,通过研究社团结构可以获取现实网络的大量有用信息。目前,对于复杂网络的社团检测,研究者们提出了大量的算法,主要有图分割法、分级聚类法、基于模块度的方法和基于统计推断的方法等。这些现有的算法大多针对无权网络,然而很多现实网络本质上是加权网络,边的权重对网络的功能和特性有着重要影响,忽略权重信息会丢掉很多有用的信息。一方面,随着现实网络的规模不断扩大,拓扑结构日趋复杂,使得我们难以掌握整个网络的信息和结构,因此需要提出有效的局部社团检测方法来解决该问题。另一方面,实际网络中存在一些节点可以同时在多个社团中,研究者将这些节点称为重叠节点,对应的社团称为重叠社团,目前已有一些重叠社团检测方法,但大多属于全局算法且主要用于无权网络的检测,无法适用于检测规模巨大、结构复杂、全局信息不可知的加权网络的重叠社团结构。因此,本文针对加权网络,进行了局部社团检测和重叠社团检测的研究。在局部社团检测方面,提出了一种简单快速的有效方法,在该方法中定义了节点划分到社团中的社团强弱度系数,扩展了P强度评价指标用于加权网络,通过计算机生成网络和现实网络进行了验证,并和现有的一些方法进行比较,结果表明该算法具有较低的时间复杂度,能准确检测网络的社团结构。在重叠社团检测方面,以加权网络的局部社团检测方法为基础,通过改进模块度函数,基于社团强弱度及模块度优化的思想,准确检测重叠节点,并且利用归一化社团属于度的计算方法得出重叠节点的模糊系数,最后对计算机仿真网络和现实网络进行实验分析,验证了算法的有效性和准确性,克服了已有重叠社团检测方法大多是针对无权网络全局信息的不足。本文第一章研究了复杂网络社团检测的研究背景、意义和现状,介绍了本文的研究内容、创新点及全文的结构。第二章研究了复杂网络的拓扑特性和常用模型,社团的定义及社团检测算法的衡量指标。第三章针对加权网络进行分析,提出了基于社团强弱度系数的局部社团检测方法。第四章结合本文局部算法的特性,定义了重叠节点的模糊系数,提出了一种加权网络的局部的重叠社团检测方法,并且对仿真网络和真实网络进行实验分析,与已有算法进行比较,验证本文算法的快速有效性。最后总结本文的研究成果,并进行了展望。