基于谱聚类的动态网络社区演化分析算法

针对复杂网络社区受到个体兴趣和迁移的影响随着时间推移而演化的问题,提出一种基于谱聚类的动态网络社区演化分析算法,试图揭示动态网络社区结构随时间的演变过程.算法融合当前时刻快照拓扑结构和上一时刻社区结构两个因素,并用随机分块模型和Dirichlet分布分别对上述两个因素建模,从而将社区演化分析形式化为优化问题.从理论上验证了社区演化分析与谱聚类是等价的,为利用谱聚类解决社区演化分析奠定理论基础.在合成数据集上的实验结果表明,相比于以规格化割为目标的谱聚类,所提方法能显著提升动态社区检测的准确性和稳定性.     

动态加权网络中的演化社区发现算法研究

在动态网络中发现社区结构是一个非常复杂而有意义的过程,可以更好地观察和分析网络的演化情况。针对动态加权网络中的社区发现问题,提出了一种结合历史网络社区结构的算法,叫做动态加权网络中的演化社区发现算法（ECDA）。该算法分为两步：结合历史社区和网络结构信息,计算当前时间跳的输入矩阵;然后通过该输入矩阵计算得到结合历史时间跳信息的社区划分结果。该算法有以下优点：可以自动发现动态加权网络中每个时间跳的社区结构;对网络结构的变化和社区结构的变化具有较高的敏锐性。在人工数据集和真实数据集中进行了实验,实验结果证明该算法可以有效地发现动态加权网络中的社区结构,与其他算法相比具有较好的竞争力。     

基于节点动态属性相似性的社会网络社区推荐算法

社区推荐帮助用户寻找感兴趣的社群,是社会网络分析的重要内容。根据社会网络的动态变化特性,通过分析网络的动态演变过程、网络个体的行为特征及个体间联系的变化,研究动态社区及其个体的动态特性的形式化描述方法,提出了节点（个体）间的动态属性相似度计算方法和基于节点（个体）间的动态属性相似度计算的社区推荐算法,可以克服通过个体的直接联系进行社区推荐的局限性。实验结果表明,应用本算法进行社区推荐的准确率有较大提高,能有效应用于动态社会网络的社区推荐。     

一种新型的层次化动态社区并行计算方法

文中提出了一种可并行分解的层次化动态社区发现算法D-SNCD(Dynamic Social Network CommunityDiscovery).D-SNCD算法充分利用复杂动态社会网络变化的局部性,对算法生成的层次化社区树HOT(Hierar-chical cOmmunity Tree)的分枝进行选择性更新.与传统的对动态社会网络直接采用快照方式进行社区发现相比,D-SNCD算法在效率上取得了明显的提高.由于D-SNCD是对已有的静态社区并行计算方法P-SNCD(ParallelSocial Network Community Discovery)的进一步扩展,因而D-SNCD保持着P-SNCD算法的高扩展性和高分辨率等优点.另外,D-SNCD算法对用户参数输入要求简单.严格的数学证明和充分的实验数据保证了整个算法的正确性和有效性.     

基于结构稳定性校准的在线式社区识别

本文探讨在线社会网络的社区识别问题, 重点研究网络演变特性对社区结构产生的影响. 首先基于节点的邻域倾向性提出社区稳定性的概念并给出稳定社区的快速识别算法, 然后设计了一种基于事件的社区稳定性校准算法以此识别新网络的社区结构. 由于算法的局部搜索策略, 该方法无需在新时间片段重复执行, 并且可以在无参数条件下识别加权网络中具有任意形状的社区结构. 在人工合成网络和真实网络上的实验结果验证了算法的可行性和有效性.     

IC:动态社会关系网络社区结构的增量识别算法

社会关系网络(SNS)中社区结构的识别有助于得出有意义的个体间活动模式和社会发展规律,传统的静态SNS社区结构识别的方法不能发现SNS的变化规律,而最近受到广泛关注的动态SNS社区识别方法普遍存在可扩展性差的缺点.描述了动态SNS的数学模型,并在此基础上提出了动态SNS中发现社区结构的增量式新方法.提出方法利用动态网络时间局部性即相邻采样时刻网络变化不大的特点,通过增量分析避免对整个网络中的个体全部重新划分,达到较高的算法效率.分析和实验结果表明,效率高于现有方法,在大规模网络上(105结点量级)效率提升在一个数量级以上,发现的社区结构很好地反映出社会关系网络的本质结构.     

复杂网络社区发现研究进展

近年来,随着现代网络通信和社会媒体等技术的飞速发展,复杂网络成为多学科交叉研究的热点之一,社区发现是复杂网络中的一个重要问题,对其进行研究具有重要的理论意义和应用价值。该问题吸引了多个学科领域的众多学者的关注,并且已有许多社区发现算法被提出。已有的社区发现综述多是侧重某一方向或特定领域展开,基于此,文中在之前工作的基础上,对国内外社区发现工作进行了深入调研,较全面地阐述了复杂网络社区发现的研究现状。首先,针对不同网络结构,给出社区发现的问题定义和主要的评价指标。然后,介绍了不同网络结构中的经典社区发现算法,包括同质网络中的全局社区发现、局部社区发现算法,异质网络中的二分网络、三分网络和多分网络中的社区发现,结合节点内容和连接结构的社区发现算法,以及动态网络中的社区发现和社区演化工作。最后,简要介绍了社区发现的典型应用,包括影响最大化、链路预测和情感分析领域的应用。此外,探讨了当前社区发现研究面临的主要挑战,试图为社区发现研究领域勾画一个较为清晰和全面的轮廓,为初学者提供指引。     

社交网络中一种基于模块化的社区检测算法

现有社区检测算法无法对社交活动和交互行为迅速发展的动态社交网络进行有效检测。为此,提出一种社区快速检测算法。使用现有网络知识确定的网络结构来更新网络社区,利用模块化技术自适应地检测和跟踪动态在线社交网络的社区结构。基于现实世界的动态社交网络对该算法进行测试,实验结果表明,使用该算法作为社区检测内核的社交感知路由策略,其性能要优于MIEN算法和Blondel算法。     

在线社交网络社区的启发式挖掘框架

指出基于全局优化的社区挖掘方法的不足,给出OSNs网络及其社区挖掘的形式定义,提出一个启发式社区挖掘框架,在此框架下对包括LWP,Clauset,Schaeffer,Papadopoulos,Bagrow与Chen在内的6种启发式社区挖掘算法进行分析比较.通过3个真实OSNs网络的实验比较,验证了启发式社区挖掘框架的可行性,在结果社区有效性与时间效率上对6种启发式算法进行比较,实验结论为网络社区挖掘的工程实践与理论研究提供了借鉴.     

在线社会网络的动态社区发现及演化

在线社会网络研究中,动态隐含社区或群组结构的发现及演化探测是一个十分关键的核心问题,它对于在中观(Mesoscopic)视图观察在线社会网络隐结构特征、预测演化趋势、掌控网络势态、发现网络异常群体事件等具有重要意义.文中首先分析了动态社区发现和社区演化研究的关系,给出动态社区研究中关键挑战问题;然后根据问题背景的不同,从“同构社会网络的动态社区研究”和“异构社会网络的动态社区研究”两个方面进行国内外相关研究现状的阐述和分析,其中,在“同构社会网络的动态社区研究”中,根据评价方法的差异和关注问题的不同将当前相关研究分为基于时空独立评价、时空集成评价、统一评价和增量式算法4大类进行综述,同时对动态社区发现的重要应用——异常群体发现的研究进行介绍;最后对在线社会网络动态社区领域的难点和发展趋势进行分析和展望.     

网络社区及其链接可视化研究

针对网络社区的主题特点,提出一种网络社区可视化方法。首先分析网络社区及其特点,然后提出一种网络社区可视化方法,通过该网络社区可视化方法,用户能够更加清晰掌握网络层次组织结构。对社区之间的链接进行可视化,使用户能够直观获得社区的联系。并且基于OpenGL实现了网络社区可视化方法,对某论文搜索网的文档数目进行可视化,从可视化效果看,用户能够清晰得到论文不同主题的发展动态。该可视化方法可以运用于可视化导航,使用户实时掌握所处的社区主题。     

复杂网络健壮社团挖掘算法

提出了一种基于贝叶斯网络的健壮社团挖掘算法,通过对每个普通社团分别构建贝叶斯网络,并根据条件概率表和证据信息进行推理,得到贝叶斯网络中每个节点隶属于健壮社团的后验概率以提取健壮社团。实验结果证明了该方法对健壮社团发现的有效性。     

复杂网络社区挖掘综述

复杂网络社区挖掘是近10年来多学科交叉的前沿研究热点之一,其研究不仅有重要的理论意义,而且有广泛的应用前景.介绍了社区挖掘及重叠社区挖掘的研究背景和研究意义,分析了研究现状,讨论了该研究所面临的一些主要问题及未来的发展方向.同时,为了对不同的社区挖掘算法进行更好地评估,选择了有代表性的6个社区挖掘算法和3个重叠社区挖掘算法进行测试,并给出了对比分析结果,试图为这个新兴研究领域勾画出一个较为全面和清晰的轮廓.     

复杂网络中的邻域重叠社团结构探测

网络,数学家们称其为图,它为许多复杂系统的结构提供了一个很好的抽象,从社会网络、计算机网络,到生物网络以及物理系统的状态空间。在过去的几十年里出现了许多确定网络系统拓扑结构的改进实验,但对实验产生的数据进行科学的分析,仍然存在本质的挑战。目前的社团检测中主要存在两个问题:一是不知道网络中有几个社团;二是网络中的顶点可能属于不同的社团,也就是社团中存在重叠结构。为了了解各种重叠社团检测算法的思想、实现步骤、优缺点比较、算法应用,文中对邻域重叠社团检测算法进行了深入的分析,以k-means算法分析了经济网络,同时采用Silhouette指标解决了最佳聚类数的问题,并通过仿真实验证明了此算法的可能性。     

LPX: Overlapping community detection based on X‐means and label propagation algorithm in attributed networks

Traditional community detection methods in attributed networks (eg, social network) usually disregard abundant node attribute information and only focus on structural information of a graph. Existing community detection methods in attributed networks are mostly applied in the detection of nonoverlapping communities and cannot be directly used to detect the overlapping structures. This article proposes an overlapping community detection algorithm in attributed networks. First, we employ the modified X‐means algorithm to cluster attributes to form different themes. Second, we employ the label propagation algorithm (LPA), which is based on neighborhood network conductance for priority and the rule of theme weight, to detect communities in each theme. Finally, we perform redundant processing to form the final community division. The proposed algorithm improves the X‐means algorithm to avoid the effects of outliers. Problems of LPA such as instability of division and adjacent communities being easily merged can be corrected by prioritizing the node neighborhood network conductance. As the community is detected in the attribute subspace, the algorithm can find overlapping communities. Experimental results on real‐attributed and synthetic‐attributed networks show that the performance of the proposed algorithm is excellent with multiple evaluation metrics.     

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

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

动态社区发现方法研究综述

随着社交媒体多样性的增加,实时分析社交网络的需求不断增大,动态社区发现的研究受到了广泛的关注。已有的社区发现综述多是侧重静态社区发现,以及相关方法的探讨,无法进行网络演化分析,此外社区的实体数据往往具有交叉更替性和时序性,因此对动态社区发现的研究现状进行分析和综述。首先,基于复杂网络的研究背景,提出了通用的动态社区发现研究框架;接着,形式化表示动态社区发现的相关定义,并从网络层面和节点层面对动态社区演化进行详细分析;然后,根据架构和技术的不同,对动态社区发现方法进行归纳分类,并结合常用数据集和评价指标对经典静态社区发现算法进行定性和定量分析;最后,介绍了社区发现的典型应用场景,探讨了当前动态社区发现研究面临的主要挑战,针对性地提出了相关解决方案,为动态社区发现研究领域勾画出较为清晰和全面的研究方向。     

复杂网络聚类方法

网络簇结构是复杂网络最普遍和最重要的拓扑属性之一,具有同簇节点相互连接密集、异簇节点相互连接稀疏的特点.揭示网络簇结构的复杂网络聚类方法对分析复杂网络拓扑结构、理解其功能、发现其隐含模式、预测其行为都具有十分重要的理论意义,在社会网、生物网和万维网中具有广泛应用.综述了复杂网络聚类方法的研究背景、研究意义、国内外研究现状以及目前所面临的主要问题,试图为这个新兴的研究方向勾画出一个较为全面和清晰的概貌,为复杂网络分析、数据挖掘、智能Web、生物信息学等相关领域的研究者提供有益的参考.     

社交网络中的社团隐私研究综述

社团是社交网络的重要特征,社团检测技术的发展给网络用户带来隐私泄露的危险。如何保护敏感的社团信息不被泄露,保障用户与社团安全已经成为网络安全领域的研究热点。近几年,社团保护技术取得了初步进展,但针对社交网络中的社团隐私或社团安全研究进展综述较少,不利于该研究方向的长远发展。因此,主要针对社团结构隐私方面的研究进展进行综述,对最新的相关研究成果进行系统地归纳、总结、比较,并展望了未来的研究方向。     

The new neighbourhood in the internet era: network communities serving local communities

The past two decades have witnessed many attempts to transform online communities in new neighbourhoods of the Internet era. In particular, one of the most interesting applications of Internet Technologies in this field have been ‘network communities’, that differ from online communities because they refer to a specific territory and, for this reason, serve as a social catalyst for the corresponding territorial community. Network communities, as virtual neighbourhoods, have the purpose of allowing a better understanding of physical ones, contributing to the creation and the proliferation of services most suited to the needs of residents. For this reason, municipalities and local governments should consider the opportunity to exploit network communities as useful tools for local community management. Following this lead, this article analyses a real case study and highlights the existence of a positive correlation between a constructive utilisation of a network community by its members, their sense of community and the degree of their involvement in local problems.