关键词： 社会网   社团检测   标签传播   相似度   核心节点  

摘要： 随着社会的不断进步和科技的发展,人们的沟通交流也逐渐频繁起来,尤其是一些社交网站及社交软件的兴起,使人们的联系更加频繁密切,逐渐形成一个大的社会网络。社团结构被认为是社会网的一个重要性质,检测网络中的社团结构对于理解社会网的结构和功能都有重要意义。本文主要针对社会网中社团检测问题进行研究,主要包括以下几个方面内容:首先,对传统的标签传播算法进行了研究,该算法在标签传播过程中将所有节点的重要性视为同等,并且存在很多的随机性,这样使检测到的社团结果质量不高。本文提出了一种基于亲密度的标签传播社团检测算法,根据节点的重要性给出了局部中心节点的概念,对这些局部中心节点分配唯一的标签,可以减少传播过程中很多不必要的判断开销,提高效率;同时在标签更新的过程中考虑节点的亲密度,这样避免了节点在更新标签过程中的随机性,从而提高算法的稳定性,提升算法检测社团的质量。其次,目前的关于相似性的社团检测方法仅从节点之间的相似度进行考虑,本文提出了基于改进节点相似度的社团检测算法,该算法在Jaccard相似度的基础上,考虑节点之间边的重要度,给出节点间的综合相似度的定义,通过计算比较节点周围的邻居社团内节点总相似度,将节点划分到社团内相似度较大的社团中。通过在真实网络和人工合成网络中进行实验,表明算法具有很好社团检测效果。最后,通过对真实网络的观察发现,社会网络中每个节点的重要性都是不相同的,通常影响力越大的点在社团中占有更重要的中心性,文章提出一种基于核心节点的社团检测算法,首先通过计算节点的局部影响力找到核心节点,其次是通过这些核心节点检测到局部核心社团,最后检测出网络中的所有社团结构。该算法属于基于局部的检测社团算法,不用知道社团数量,同时具有很好的计算效率和检测质量。

关键词： 社会网络   社团检测   社团演化   核心节点  

摘要： 随着互联网络技术的发展,网络技术研究成果成为了人们生活中不可缺少的部分。微信、QQ、微博、博客、论坛、邮箱等现代网络交流通信技术的发展使人与人之间形成了很多错综复杂的网络,而这些网络中往往隐藏着大量有价值的信息。社会网络分析方法使用数学、生物、物理等领域的方法来分析社会网络中的关联关系。社团结构检测做为社会网络分析的一个重要研究方向,能够检测网络中联系紧密的节点集合,挖掘网络中有价值的信息。由于早期网络规模较小和人们对网络社团结构认识的局限性,研究人员的注意力主要集中在静态小规模的社会网络社团检测上。随着网络规模的急剧增大和社团演变特性越发明显,传统的静态社团检测方法已无法满足当前社会网络分析的需要。本论文的主要研究工作是针对大规模社会网络,提出一个基于增量聚类的快速社团检测框架。该框架包括CCDE和FICET两个算法,分别用以探测大规模网络中的社团结构和跟踪社团结构动态演变趋势。本论文取得的创新性成果如下:(1)提出一个基于核心社团扩展的静态社团检测(CCDE)算法。CCDE算法采用改进的PageRank算法得到网络的核心节点,使其构成核心网络;使用层次聚类的方法对核心网络进行核心社团检测;扩展核心社团从而得到网络的整体社团结构。通过引入核心网络、核心社团的概念,CCDE算法与经典静态社团检测算法相比,能够在保证较小的时间开销下获得有效、准确的社团检测,适用于大规模网络的检测需要。(2)提出一个基于增量聚类的动态社团检测(FICET)算法,该算法在CCDE算法的基础上进一步研究动态社团检测问题。FICET算法引入社团结构偏移量的概念,对相邻时间段的核心网络节点和边的变化进行增量处理,快速得到当前时间段的网络的核心社团结构,再扩展核心社团结构从而得到网络的整体社团结构。大量仿真数据集和真实网络数据集上的对比实验表明,该算法具有较高的算法准确性,能够同时适应缓慢演化和快速演化的两种动态网络,并能够满足大规模动态网络的检测需要。

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

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

关键词： 在线社会网络   社团检测   多属性   半监督   动态   图流   非负矩阵分解   局部信息  

摘要： 近年来,网络技术的飞速发展和在线社会网络的日益普及,使得数以亿计的网络用户能够更为便捷的进行网上办公、学习、社交和娱乐,通过这些“在线”的交互方式,人们在形成现实生活中复杂社会关系的同时,也构建了丰富多样的新型在线社会关系。在线社会网络的兴起引起了研究者们的踊跃关注,其中社团结构是网络社会关系的基本组织结构,针对在线社会网络中的社团进行检测,是对在线社会网络进行挖掘分析的前提和基础,有助于揭示网络的构成和特征,进而理解网络的运行方式,具有十分重要的应用价值和研究意义。 在线社会网络通常具备属性多样化、结构动态变化和规模日益庞大等突出特点,给社团检测研究提出了新的问题和挑战,传统针对单质、静态和全局的社团检测方法难以有效应对这些处理需求,迫切需要提出新的模型和方法。本课题以在线社会网络数据挖掘为应用背景,依托于国家科技支撑计划项目“面向融合网络的舆情监控”和国家863计划项目“公众通信网络用户关系与行为分析技术”,对新型在线社会网络中社团检测关键技术进行研究,为在线社会网络社团检测所出现的新问题进行模型建立和解决。具体地,本文的主要工作和成果如下: 1.介绍了课题的研究背景与意义,总结和梳理了社团检测的经典模型和方法,深入分析了在线社会网络所呈现出的新特性,并指出了课题研究所要解决的关键问题,探索了在线社会网络社团检测的新模型和解决思路,进而明确了课题的研究范围和技术路线。 2.针对网络中结构拓扑属性和节点本身内容属性缺乏有效融合分析问题,提出了一种基于联合矩阵分解的多属性网络社团检测方法(CDJMF,Community Detection based on Joint Matrix Factorization)。该方法首先根据节点的自身内容属性进行相似度计算,获取节点之间的相似度矩阵描述;然后结合反映网络拓扑信息的邻接矩阵进行联合矩阵分解模型的构造,进而将两类信息作为社团检测的协同学习项进行统一表述;最后通过对联合特征矩阵的迭代分解获取同一个社团检测结果。该方法通过对不同信息源进行融合分析,提高了多属性网络中社团检测方法的有效性。在网络中的实验结果表明,CDJMF相比已有方法具备更高的社团检测质量。 3.针对动态网络中难以有效结合不同时刻的结构信息进行社团检测问题,提出了一种基于图正则化的半监督动态社团检测方法(SDCD-NMF,Semi-supervised Dynamic Community Detection based on Non-negative Matrix Factorization)。该方法首先提取了历史时刻网络中所包含的有效稳定结构单元;然后将其作为正则化监督项来指导当前时刻网络静态图进行社团检测。该方法将历史时刻稳定信息和当前时刻的结构信息在同一个矩阵分解架构中进行融合分析,为动态网络社团检测提供了新的研究思路和框架。实验表明,所提方法有效利用了历史时刻网络中的稳定信息,提高了社团检测精度。 4.针对在线社会网络中数据流式到达的实时处理需求,提出了一种基于在线非负矩阵分解(ONMF,Online Nonnegative Matrix Factorization)的图流社团检测方法。该方法首先将网络中持续到达的图数据按照流式数据进行缓存处理;然后借鉴梯度下降思想,基于在线非负矩阵分解架构,根据实时到达的图流序列,实时迭代更新已有的社团归属矩阵,并通过有效的学习率和缓存策略设置,保证了图流处理的收敛性和合理性。在真实网络数据集上的实验表明,所提方法能够应对动态到达网络数据流中的实时社团检测需求,并取得了较高的社团检测精度。 5.针对从局部信息出发社团检测中存在对初始节点位置敏感、拓扑信息难以有效利用的问题,提出了一种基于影响力节点集扩展的局部社团检测方法(IN-LCD,Local Community Detection based on Influential Nodes)。该方法首先定义了节点的局部影响力指标,通过该指标计算并构造了局部影响力节点子集;然后从影响力节点子集开始,以迭代更新的方式,进行连续的社团扩张;最后通过所定义的局部相似性指标来精确控制社团的扩张过程,进而完成整个局部社团的获取。在真实和人工网络数据集上的实验表明,所提方法识别性能优于已有的最佳局部社团检测方法,能够更好地利用局部信息进行社团检测。

关键词： 社团检测算法   局部检测   可视化   JUNG  

摘要： 有效发现与理解社团结构是复杂网络研究中非常重要的问题。此文分析与比较了传统的GN算法、Fast-Newman算法和CNM算法,基于JUNG框架设计与开发了社团检测可视化平台。该平台首先实现了上述三种算法,并与此文提出的局部社团检测算法(CDAMDL算法)在标准网络数据集上进行了分析测试。实验表明,在检测效果,计算耗时等方面,CDAMDL算法均优于传统算法。同时该平台提供了透明、直观的社团检测结果和评价,为复杂网络社团结构分析提供了依据。

关键词： 矩阵分解   节点属性   社团检测  

摘要： 发现复杂网络中的社团结构在社会网络、生物组织网络和在线网络等复杂网络中具备十分重要的意义.针对社交媒体网络的社团检测通常需要利用两种信息源:网络拓扑结构特征和节点属性特征,丰富的节点内容属性信息为社团检测的增加了灵活性和挑战.传统方法是要么仅针对这两者信息之一进行单独挖掘,或者将两者信息得到的社团结果进行线性叠加判决,不能有效进行信息源的融合.本文将节点的多维属性特征作为社团划分的一种有效协同学习项进行研究,将两者信息源进行融合分析,提出了一种基于联合矩阵分解的节点多属性网络社团检测算法CDJMF,提高了社团检测的有效性和鲁棒性.实验表明,本文所提的方法能够有效利用节点的属性信息指导社团检测,具备更高的社团划分质量.

关键词： 节点亲密度   节点度   加权网络   模块度   社团检测  

摘要： 社会网络是现实社会在网络空间的延伸,研究社会网络的结构特征对于发现网络结构、预测网络行为、保障网络安全有着重要的意义.社团结构是社会网络最重要的一种结构特征.近年来,研究人员提出了大量的社团检测算法,但大多集中在无权网络,不能处理网络中越来越复杂的连接关系.为了衡量有向加权网络中节点之间的关联强度,提出了一种新的节点亲密度定义,在此基础上设计了一种基于节点亲密度和度的社团结构检测方法(community detecting method based on node intimacy and degree,CDID),并在真实的社会网络数据集上进行了实验验证.与传统的社团检测方法相比,CDID方法能够获得更加准确的社团划分结果,并为无向无权、有向无权、无向加权、有向加权网络的社团划分提供了一种统一的解决方法.

关键词： 维基百科   知识网络   复杂网络   人物关系   社团检测  

摘要： 已有的针对维基百科知识网络的研究只集中在宏观层面上,为深入挖掘维基百科中更细粒度的领域知识,采用复杂网络的分析方法,对从维基百科中抽取的人物关系知识网络进行分析研究。计算其多种网络参数,研究其小世界性和无标度性,发现人物关系知识网络是一个典型的复杂网络,具有和其它社会网络类似的网络特征。进一步挖掘网络中的重要节点,发现维基百科内容的丰富程度与普通百姓的兴趣点是密切相关的。最后对网络进行社团检测,发现同一社团中的成员聚集在一起是可以解释的,从而验证了利用社团检测算法挖掘出的社团的合理性。

关键词： 复杂网络   二分网络   遗传算法   社团结构  

摘要： 目前二分网络社团检测研究处于探索阶段,评估标准和检测方法较少,模块度值具有局部性且偏差较大,检测结果不稳定。针对上述问题,提出一种基于遗传算法优化二分网络模块度的检测方法,依据节点相似度初始化染色体,通过不断改变社团个数,使用改进的遗传算法交叉、选择和变异等因子,遗传迭代获得全局模块度最大值以及对应的社团划分。仿真结果表明:能够有效检测到模块度全局最大值以及对应的社团个数和社团划分,社团划分更加精准,算法具有较强的鲁棒性和抗干扰能力。

关键词： 社团结构检测   节点相似度   线性阶时间复杂度   稳定  

摘要： 针对目前社团结构检测算法计算量大以及不稳定的问题,在经典的Newman快速与LPAm的基础上提出了一种基于局部信息的社团发现新算法。算法利用节点度和共享邻居数定义节点相似度,并结合两个预设参数,逐步优化社团结构。性能分析证明,该算法不仅具有线性阶时间复杂度,而且是一种稳定的算法。实验结果表明,该算法在准确度上优于Newman快速和LPAm,且可行与有效。