关键词： 复杂网络   社团检测   重叠社团   局部扩充  

摘要： 基于局部扩充的重叠社团检测算法由单个节点或团出发,不断添加新的节点而获得最终的社团划分,但现有算法均为每次添加一个节点,没有充分考虑所添加节点的局部信息,从而影响了社团检测结果的准确性.为此,文中提出了一种基于单步添加团的重叠社团检测算法,该算法从一个团开始,通过不断添加此团邻居内适应度增值最大的团,使算法在局部扩充时不仅考虑了所添加节点与已有社团的连接紧密性,而且考虑了所添加节点内部的连接情况.在真实网络和计算机生成网络上的实验结果表明,与现有基于局部扩充的重叠社团检测算法相比,文中算法可以更准确地检测出复杂网络中的重叠社团.

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

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

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

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

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

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

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

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

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

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

关键词： 链接预测   社团检测   监督学习   社会网络分析  

摘要： 随着信息社会的发展,拥有海量数据的复杂网络不断出现,如何从这些网络中挖掘出有价值的信息是一个十分艰巨的任务。链接预测是数据挖掘领域的重要分支,也是社会网络分析的关键任务之一。链接预测研究如何利用网络中已有的信息预测可能存在或即将生成的链接,对于理解网络的结构和发现网络中隐藏的信息有着重要的理论与现实意义。近年来,链接预测已然成为数据挖掘领域的研究热点问题,被广泛应用于社会网络、生物网络和信息网络等多种现实网络当中。目前,国内外关于链接预测的研究主要是基于节点相似度的方法,因为该类方法具有较低的时间复杂度和良好的预测效果。随后,监督学习技术被应用于链接预测任务中,用于学习网络结构和链接形成之间的规律。然而,已有的方法存在一定的局限性,即仅仅考虑节点与邻居节点之间的局部关系,而忽略了节点与其他非邻居节点之间的全局关系。事实上,现实网络中普遍存在社团(Community)的结构,同一社团中的节点之间连接紧密而不同社团中的节点之间连接松散。社团对链接的形成有重要的影响,同一社团中的节点对一般更容易形成链接。因此,如何利用网络中的社团信息改进现有的链接预测算法是一个值得深入研究的问题。针对链接预测研究的问题与挑战,本文将社团信息用于链接预测,在基于监督学习的链接预测框架下,提出了一种采用社团信息改造样本特征的链接预测方法(CR-LiP)和一种采用社团信息扩充样本特征的链接预测方法(CE-LiP)。最后在ACF数据集与FaceBook数据集中进行了仿真实验,将CR-LiP、CE-LiP与相关方法进行了比较。实验结果表明,抽取网络中的社团信息扩充节点对的描述子,可以改进学习器的性能,提高链接预测方法的准确率。

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

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

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

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

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

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