基于熵加权属性子空间的目标社区发现

该文提出一种基于熵加权属性子空间的目标社区发现方法,挖掘与用户偏好相关的社区。首先,从属性和结构两个方面综合考虑节点间的相似度,利用用户给定的样例节点及其邻居扩展得到目标社区中心点集;其次,在中心点集上,设计一种熵加权的属性权重计算方法,得到目标社区的属性子空间权重;再次,利用目标社区的属性子空间权重,基于节点的属性和结构相似度重写网络中边的权重;最后,定义社区适度函数并结合重写后网络中边的权重改进社区适度函数,以中心节点集为核心,挖掘基于用户偏好的内部连接紧密且与外部分离较好目标社区。此外,该方法可以扩展到网络中多个社区发现及离群点检测任务中。在人工网络和真实网络数据集上的实验结果验证了该文所提算法的效率和有效性。     

基于二部图表示的属性网络社区发现算法

属性网络社区发现是网络数据分析中的一项重要研究内容。为了提高社区发现的准确性，现有算法大多通过融合拓扑信息和属性信息对属性网络进行低维表示，然后基于低维特征进行社区发现。然而，这类算法通常基于深度模型进行表示学习，缺乏一定的可解释性。因此，文中提出了一种基于二部图表示的属性网络社区发现算法，以提高社区发现结果的准确性和可解释性。首先，分别基于属性网络的拓扑信息和属性信息计算网络中各个节点作为代表点的概率，通过两类信息融合选出一定比例的节点作为代表点；其次，基于拓扑结构和节点属性计算各个节点到代表点的距离，构建二部图；最后，基于二部图利用谱聚类算法进行社区发现，得到最终结果。在人造属性网络和真实属性网络上与已有的属性网络社区发现算法进行实验比较分析。实验结果表明，所提算法在标准化互信息、调整兰德指数等评价指标上均优于已有算法。     

基于桥系数的分裂社区检测算法研究

研究社区结构有助于揭示网络结构和功能之间的关系,而社区检测是社区结构研究的基础和核心。该文定义了一种聚集度桥系数,将其应用到社区检测中,设计出一种分裂社区检测方法,包括分裂和合并两个算法。分裂算法使用桥系数识别社区间边,通过迭代删除社区间边分解网络,从而发现网络中的社区结构;合并算法根据社区连接强度合并社区,可以揭示社区结构中的分层嵌套的现象。在六个社会网络数据集上的实验表明,本文算法可以有效的将网络分裂为有意义的社区,并且准确性接近或超过经典的社区检测算法。     

基于弱概念相似度的组推荐方法

网络数据下的概念认知与知识发现是网络背景下机器学习和人工智能的重要研究方向,已被引入到推荐系统研究中。现有的基于概念格的推荐方法忽视了节点之间的网络结构关系,同时构造概念格的效率低且构建概念集合的约束条件较严,在大规模的社交网络中难以实现。为解决这些问题,本文在网络形式背景的框架下,综合复杂网络的拓扑结构和弱概念相似度,提出了基于弱概念相似度的组推荐算法。首先,定义属性度、属性密度来描述属性的重要性,通过改进的节点影响力来确定专家节点;其次,利用专家节点划分社区,在划分的社区中通过属性弱概念下限相似度进行组推荐研究,进而获取推荐规则并对相应社区进行组推荐;最后,利用MovieLens数据集和Filmtrust数据集分析了各参数对本文所提算法的影响,并确定了参数的合理取值。将本文所提算法与其他推荐算法进行比较测试,实验验证了本文算法的有效性。     

基于圈结构的LPANNI优化算法

针对重叠社区发现准确率提升问题,提出了一种基于圈结构的LPANNI优化算法CLPANNI（cycle label propagation algorithm with neighbor node influence）。该算法通过挖掘节点的最小圈信息,依据圈比指标衡量节点的重要性并按升序进行标签更新,增加了标签传播过程的稳定性,按照邻居节点影响力大小加权接收邻居节点传递的标签。与四种基准算法在NMI_LFK、NMI_MGH、MOV指标下进行测试比较,CLPANNI算法在社区发现准确率方面表现较好。实验结果表明,该算法能够有效探测网络重叠社团结构,发现网络的紧密子团,识别的社团分布与真实网络结构更为接近。     

基于染色随机游走的可重叠社区发现

社区发现是一个基础性的且被广泛研究的问题。现有的社区发现方法大多聚焦于网络拓扑结构,然而随着真实网络中实体可用属性的激增,捕获图中结构和属性的丰富交互关系来进行社区发现变得尤为必要。据此面向属性图提出了一种基于染色随机游走的可重叠社区发现算法OCDC,该算法解决了传统的基于随机游走的社区发现算法利用结构转移矩阵造成社区发现效果不佳的问题。具体地,首先利用经典的初始种子策略选出网络中差异度较大的节点,在此基础上设计种子替换策略,挖掘网络中质量更佳的种子替换路径集合对初始种子集合进行替换;其次构建结构-属性交互节点转移矩阵并执行染色随机游走过程得到高质量种子节点的染色分布向量;最后基于融合结构和属性的并行电导值对社区进行扩展。在人工网络和现实网络上的实验表明,本文提出的算法能够准确地识别属性社区并显著优于基准算法。     

基于属性自表达的低秩超图属性选择算法*

针对高维数据具有低秩形式和属性冗余等特点,提出一种基于属性自表达的无监督超图属性选择算法。具体地,该算法首先利用属性自表达特点用其他属性稀疏地表达每个属性,此自表达形式使用低秩假设寻找高维数据的低秩表示,然后建立超图正则化因子保持高维数据的局部结构,最后利用稀疏正则化因子进行属性选择。属性自表达特性确定属性的重要性,低秩表示相当于考虑数据的全局信息进行子空间学习,超图正则化因子考虑数据的局部结构对数据进行子空间学习。该算法实际上考虑数据全局和局部信息进行子空间学习,更是一种嵌入了子空间学习的属性选择算法。实验结果表明,该算法相比其它对比算法,能更有效地选取属性,并能取得很好的分类效果。     

基于统计推理的社区发现模型综述

社区有助于揭示复杂网络结构和个体间的关系.研究人员从不同视角提出很多社区发现方法,用来识别团内紧密、团间稀疏的网络结构.自2006年以来,提出了一些基于统计推理的社区发现方法,它们可识别实际网络中更多的潜在结构,并以其可靠的理论基础和优越的结构识别能力成为当前的主流.该类方法的主要目标是建立符合实际网络的生成模型以拟合观测网络,将社区发现问题转化为贝叶斯推理问题.首先给出社区发现中生成模型的相关定义;其次按照模型中社区组成元素将已有统计推理模型分为节点社区推理模型和链接社区推理模型,并深入探讨各种模型的设计思想及实现算法;再次,总结各模型适用的网络类型及规模、发现的社区结构、算法复杂度等,给出一种选择已有基于统计推理的社区发现模型的方法,并利用基准数据集对已有典型统计推理模型进行验证及分析;最后探讨了基于统计推理模型的社区发现存在的主要问题和未来发展的方向.     

基于子图结构的局部社区发现算法

局部社区发现算法通常选取种子节点进行社区发现,针对现有重叠社区发现算法中种子节点选取时有效性不足的问题,提出了一种基于子图结构的局部社区发现算法(Subgragh Structure Based Overlapping Community Detection,SUSBOCD).该算法提出了一种新的节点重要性度量指标,不仅考虑了节点的邻居数量,同时也考虑了邻居间的链接紧密程度.首先,选取未被访问且重要性最大的节点以及与其最为相似的邻居节点,将该两个节点及其公共邻居节点合并形成一个初始种子子图,该过程迭代运行直到所有节点均被访问;其次,根据种子子图的邻域信息进行相似度判断,若相似则进行合并,从而形成初始社区结构,持续扩展该过程直到所有种子子图均被访问;最后,对社区进行优化处理,若存在未分配社区的节点,则将其加入到最相似的初始社区,再合并重叠度较高的初始社区结构.在人工数据集和真实数据集上,对所提算法进行实验验证,实验结果表明,与其他重叠社区发现算法相比,SUSBOCD算法在ONMI,EQ和Omega这3个评价指标上均有所提升,即该算法能有效地提高重叠社区的划分质量.     

面向属性网络的可重叠多向谱社区检测算法

谱社区检测算法多基于结构对网络进行划分,往往受限于划分数量且难以控制重叠程度。设计了面向属性网络的谱社区检测算法,可将属性网络划分为任意数量的可重叠社区并有效发现离群点。具体地,首先,从结构和属性两方面综合考虑,基于加权模块度设计了最大化到节点向量化的分区映射方法;其次,给出簇中心向量的初始选择策略,并将其融合在面向属性网络的重叠度和离群度制约中,实现重叠社区的发现;再次,设计节点分配策略,计算节点与簇中心向量的内积,将节点分配给具有最高内积的社区;最后,结合节点隶属情况,高效地在属性网络中检测出结构紧密、可重叠和具有离群点的社区。此外,将本文算法应用于现实世界的多个网络,验证了本文算法的有效性和效率。     

基于权重信息挖掘社会网络中的隐含社团

社团结构是一种普遍存在于各类真实网络中的结构特性.挖掘网络的社团结构对于理解网络的功能与行为有着重要作用.然而,现有的各种社团挖掘算法仅仅基于网络拓扑结构信息,而忽视了蕴涵于真实社会网络边权信息中丰富的语义信息.目前普遍使用的基于模块性最大化的社团挖掘算法倾向于将小社团合并,这使得语义上丰富的小社团容易湮灭于基于拓扑结构信息所挖掘出的大社团中.而挖掘出这些隐含于大社团中的有着丰富语义内涵的小社团对于加深社会网络语义层面的理解有着重要作用.为此,提出一个接近线性复杂度的有权网络社团挖掘算法.通过充分利用权重信息,算法可以将社会网络划分为富含语义信息的粒度较细且相对较小的隐含社团.通过对基于DBLP作者合作网络的实证分析,证实了新算法的有效性和高效性.     

结合拓扑势与信任度调整的重叠社区发现算法

现实世界中的复杂系统可建模为复杂网络,探究复杂网络中的社区发现算法对于分析复杂网络的拓扑结构和层次结构具有重要作用。早期研究通常将网络中的节点局限在一个社区中,但随着研究的深入发现社区结构呈现重叠特性。针对现有重叠社区发现算法存在划分社区结构不稳定、忽略节点交互和属性等问题,提出一种基于网络拓扑势与信任度调整的重叠社区发现算法。融合节点的属性和结构特征计算节点的拓扑势,依据节点的拓扑势选取核心节点。从核心节点出发构建初始社区群,计算各个社区间的调整信任度,实现社区的合并与再调整,从而识别重叠社区。在多个人工模拟网络和真实网络数据集上的实验结果表明,与基于贪婪派系扩张、种子扩张等的重叠社区发现算法相比,该算法将扩展模块度最高提升至0.719,能有效识别社区结构及重叠节点,提升重叠社区检测性能。     

Toward seed-insensitive solutions to local community detection

Local community detection aims at finding a community structure starting from a seed which is a given vertex in a network without global information, such as online social networks that are too large and dynamic to ever be known fully. Nonetheless, the existing approaches to local community detection are usually sensitive to seeds, i.e., some seeds may lead to missing of some true communities. In this paper, we present a seed-insensitive method called GMAC and its variation iGMAC for local community detection. They estimate the similarity among vertices by investigating vertices’ neighborhoods, and reveal a local community by maximizing its internal similarity and minimizing its external similarity simultaneously. Extensive experimental results on both synthetic and real-world data sets verify the effectiveness of our algorithms.     

基于网络嵌入与局部合力的复杂网络社区划分算法

社区划分可以揭示复杂网络中的内在结构和行为动态特点,是当前的研究热点。文中提出了一种基于网络嵌入和局部合力的社区划分算法。该算法将网络的拓扑空间转化成欧氏空间,把网络节点转换成向量表示的数据点,首先基于重力模型和网络拓扑结构,提出局部合力和局部合力余弦中心性指标(Local Resultant Force Cosine Centrality,LFC),通过节点的LFC和节点间的距离来确定各个初始小社区的中心节点,然后将网络中其他的非中心节点划入与其最近的中心节点所在的初始小社区内,最后通过优化模块度的方法来合并初始小社区并找到最优的网络社区结构。在6个现实世界网络和可调参数人工网络上与6种知名社区划分方法进行比较,比较结果表明了新算法良好的社区划分的性能。     

社会语义网社区发现标签传递算法研究

针对在线社会网络的特性和现有社区发现算法的不足,提出一种基于语义网技术的在线社会网络社区发现算法ISLPA(Improved Semantic Label Propagation Algorithm),即一种适用于大规模在线社会网络的社区发现和标识算法。ISLPA算法对语义标签算法SemTagP进行改进,在社区划分过程中将在线社会网络视为有向加权图,通过语义网和社会化标签技术,充分结合在线社会网络丰富的语义信息和网络拓扑特征进行社区划分。ISLPA算法不需要预先设定社区数量和大小,就能实现社区发现,并能根据标签自动识别划分的社区。算法接近线性时间复杂度,具有较高的效率。通过实验表明,ISLPA算法能有效划分和标识真实在线社会网络。     

一种基于局部信息的社区发现方法

针对复杂网络中难以发现小社区的问题,在CNM算法的基础上,提出一种利用局部信息进行社区挖掘的方法。定义节点的强度及节点对社区的贡献,改进模块度使该方法能适用于带权网络。利用社区局部信息得到小社区集合,将小社区集合作为CNM算法的输入,计算小社区间的模块度增量,凝聚模块度增量小的小社区,并得到最终结果。实验结果表明,该方法具有较高的社区模块度和算法执行 效率。     

一种融合节点与链接属性的社交网络社区划分算法

针对传统社交网络社区划分算法普遍缺乏对节点属性、链接属性的综合考虑和充分表达利用节点与链接属性信息的模型和机制等问题, 提出了一种融合节点与链接属性的社交网络社区划分算法。该算法融合节点属性的相似度、节点间链接权值等链接属性信息, 定义了相似权值, 并以此为基础, 结合凝聚算法实现了对社交网络的社区划分。实验表明, 该算法对社交网络中属性比较明显的社区划分效果显著。     

基于标签传播的拓扑势社区检测算法

基于拓扑势的社区检测通过节点的链接信息构造拓扑势域,在拓扑势域内进行社区划分.但实际划分过程存在大量孤立性社区.带节点属性信息的社区检测问题作为社区的重要组成,已成为社区检测的主要研究方向.本文提出了一种结合标签传播的拓扑势社区检测算法（TPCDLP）.首先,结合标签传播思想将属性信息转换为节点间的链接权值.其次,把链接权值加入到拓扑势中构造拓扑势域.再利用核心节点进行子群社区的划分.最后,利用子群社区间核心节点的距离进行社区划分.在3个含标签属性的数据集上,与6种算法对比,该算法在改进的模块度$Q_{ov}^E$、信息熵$Entropy$、社区重叠度$Overlap$和综合指标F上表现更优.在3个真实社区上应用了该算法,并与3种算法对比,实验结果显示该算法在标准化互信息指标$NMI$上表现良好,能够有效应用于实际问题.