有向网络重叠社区的快速划分算法

随着社会的发展,数据量越来越大,网络规模也在迅速增长。作为一种研究网络结构的有效方法,社区划分对于深刻认识超大规模网络有重要的意义。在分析研究有向网络的非重叠社区划分算法和无向网络的重叠社区划分算法的基础上,提出了一种有向网络重叠社区划分的快速算法。算法根据节点的有向权值和归属度进行社区划分,并分析了有向权值和归属度对划分结果的影响,在此基础上得到了一组最优的有向权值和归属度参数。使用2个实际网络和1个人工构建网络对算法的性能进行了测试并与已有算法进行了对比。实验结果表明,所提出的算法能够有效地划分出有向网络中的重叠社区。     

基于共邻节点相似度的社区划分算法

复杂网络中的社区结构能帮助人们认识网络的基本结构及其功能。针对目前多数社区划分算法准确率低、复杂度高的问题，提出了一种基于共邻节点相似度的社区划分算法。首先，为了计算节点间相似度值，提出了相似度模型，该模型通过将被测节点对的邻居节点引入一并计算，提高了相似度度量的准确性；然后，计算节点局部影响力值，能客观地表现出节点在所处网络中的重要性；其次，结合节点相似度值和节点局部影响力值对节点进行层次聚类，完成网络社区结构的初步划分；最后，通过聚合初步划分的子社区，获得复杂网络的最优模块度值。仿真结果表明，在网络的社区特征模糊时，与新的基于局部相似度的社区发现算法（CDALS）相比，所提算法的准确率提高了14%，证明了所提提法更能够准确、有效地划分复杂网络的社区结构。     

基于信息扩散概率的二分网络社区划分算法

二分网络是复杂网络的表现形式之一,二分网络单侧节点的社区划分对研究复杂网络具有重要的实际意义.基于信息在网络中的扩散概率和模块度思想,本文提出了一个针对二分网络的社区划分聚类算法(IPS算法).该算法通过模拟信息在网络中扩散的过程,利用各个节点的信息量在网络中扩散后,每个节点收到其他节点的信息量作为社区之间合并的依据,并引入二分网络模块度作为社区划分优劣判断的依据.最后算法在典型网络上测试结果表明,该算法不仅能够精确的识别二分网络社区个数,而且可以获得高质量的社区划分结果.     

基于节点综合相似度的多标签传播社区划分算法

为了解决现有的多标签传播社区划分算法采用的随机顺序策略导致形成的社区划分结果不稳定和社区质量不够高的问题,提出了一种基于节点综合相似度的多标签传播社区划分算法MLPA-NCS。以节点潜在影响力的降序作为节点选择顺序,解决社区结果划分不稳定问题。根据节点的主题相似度和链接相关度计算出节点综合相似度,并以节点综合相似度降序作为更新节点标签时对邻近节点遍历的顺序,提高所划分社区的质量。采用真实数据集和人工网络数据,对多个算法进行对比实验,结果表明算法有效可行,社区划分结果更稳定,社区质量也更高。     

基于节点从属度的加权网络重叠社区划分算法

针对传统社区划分算法忽略现实世界网络特征导致社区划分准确率低的问题,提出了一种基于节点从属度的加权网络重叠社区划分算法。该算法提出加权网络模型,通过模型得到了能刻画出真实网络结构的加权网络;通过网络拓扑结构定义了核心社区,核心社区对社区划分的准确性有着重要作用。该算法计算节点与核心社区间的从属度,并与从属度阈值进行比较进行核心社区扩展,根据扩展模块度优化思想,通过不断地调整从属度阈值直到获得最优的社区结构,完成重叠社区划分。在人工网络数据集和真实世界网络数据集上与已有算法进行实验对比,实验结果验证了所提算法能够准确、有效地检测出重叠社区。     

一种融合邻边属性的个人社交网络社区发现算法

针对传统智能进化社区发现算法通常存在弱化节点属性和容易过早收敛等问题,提出基于邻边属性群智能聚类的个人社交网络社区发现算法NLA/SCD.在融合邻边结构及其节点属性相似特性的基础上,定义社会蜘蛛优化算法的适应度函数,并将社区模块度增量作为算子迭代准则.在雌性和雄性个体的进化与交配过程中,利用适应度函数和模块度增量函数从...     

基于社交网络节点中心度挖掘其社区框架

社区结构作为真实复杂网络所普遍具有的一个重要的拓扑特性,最近10年内得到了广泛而深入的研究。为解决社区挖掘策略时间复杂度过高、缺少与用户交互等问题,讨论了社交网络节点中心度、度的幂律分布等特性,提出了关键子网络和社区框架的概念,设计了社区框架挖掘算法MCF(Mine the Community Framework)和社区框架钻取算法DCF(Drill Down the Community Framework),其中MCF算法用于挖掘社交网络的社区框架,DCF用于对社区框架进行钻取,从不同粒度展现社区结构。实验结果和实验分析表明,MCF算法能够在较短时间内挖掘出反映复杂网络社区状态的社区框架,DCF算法可以以用户交互方式实现高质量的社区划分。     

基于主题与连接的局部社区划分算法

设计了一种基于主题与连接的局部社 区划分算法。该算法结合节点的主题相似度和连接相似度,综合计算节点间的相似度。同时 算法采用局部思想,避免了寻找初始的中心节点。此外,该算法引入了局部模块度作为社区 划分的结束判断条件。该算法被应用到参与“海地地震”相关话题讨论的Twitter微博用户 数据集上,并与单纯基于链接、单纯基于主题以及基于主题和链接的社区划分算法在同样数 据集的划分结果进行对比,结果表明：从纯度和熵的评估角度看,本文算法更具优越性。     

基于度中心性局部扩展的社区划分算法

社交网络中社区划分问题的研究不仅为网络演化、信息传播和影响力分析等方向提供了理论依据,而且在好友推荐、商业营销和舆情检测等领域有着重要应用价值.针对基于贪婪优化的社区划分算法AGSO不稳定问题,提出了一种基于度中心性局部扩展的社区划分算法(DCLE).首先计算所有节点的度中心性(Degree Centrality),其次将链接两端节点度中心性之和作为链接的度中心性并降序排序,其后将度中心性最大链接作为初始链接加入网络,最后基于贪婪策略局部扩展并迭代,得到最终的社区划分结果.通过在公开的数据集和大型人工网络上进行实验,结果表明DCLE算法能快速且准确地发掘社区结构,稳定性得到显著提升.     

带源节点的快速社区发现算法

提出了一种改进的带源节点的CNM快速社区发现算法,用于含有部分已知社区属性节点的复杂网络的社区结构划分。算法中将这部分节点作为源节点,采用模块度增量最大化为目标函数对待划分节点进行聚合,并在取得最大全局模块度值时得到社区划分结果。以深圳市手机基站用户流量网络为例,将位于各规划城市中心的基站点作为源节点引入,对城市进行区域划分。结果表明,该算法不但能够发现基于各城市中心的服务边界,也能发现一些隐含的城市区域。     

基于节点属性的社区发现博弈算法

提出一种基于节点属性的社区发现博弈算法G_NA（game algorithm based on node attributes for community detection）。将社区发现的过程看做网络中节点的博弈,当所有节点都不能提高自身收益时,博弈结束。首先,G_NA提出基于节点度属性的收益函数;然后,在迭代过程中,节点按照重要度从大到小排序,并依次选择策略提高收益;最后,将提出的算法与现有算法分别在不同的真实网络和人工网络上进行对比实验,结果表明提出的算法优于其他算法。     

基于节点依赖度和相似社团融合的社团结构发现算法

社团结构作为复杂网络的拓扑特性之一具有重要的理论和实践意义。提出一种基于节点依赖度和相似社团融合的社团结构发现算法,首先根据依赖度和相似度的定义将整个网络划分成若干个平均集聚系数较大的局部网络,构成网络的基础骨架社团;然后根据连接度的定义不断将社团边缘的节点和小社团吸收到相应的骨架网络中去,直到所有节点都得到准确的社团划分。算法在Zachary空手道俱乐部网络和海豚社会网络中进行了社团划分实验,并与GN算法和Newman快速算法进行了比较,结果表明该算法可以有效地划分社团边缘的模糊节点,社团划分结果具有较高的准确度。     

基于图遍历的局部社区发现算法

针对当前局部社区发现算法扩张速度慢不适用于大规模网络的问题,提出了一种基于图遍历的局部社区发现算法。该算法首先找出网络中度数最低的节点,以该节点为起点通过影响力函数将网络中的节点分为社区节点和边界节点,形成初步的社区划分,然后通过适应度函数确定边界节点的社区得到最终划分结果。实验结果表明,该算法在真实网络上进行测试时不仅能够有效地挖掘网络中的社区结构而且具有较快的速度。     

改进的基于局部模块度的社团划分算法

针对大多复杂网络社团划分算法不能快速发现最优节点加入社团的问题,提出一种利用节点亲密度的局部社团划分算法。引入节点亲密度的概念量化社团与邻居节点的关系,按照节点亲密度由大到小选择节点加入社团,最后以局部模块度为指标终止局部社团扩展。在真实网络和人工仿真网络进行实验,并与基于信息压缩的随机游走算法等4种典型社团划分算法相比较,所提算法划分结果的综合评价指标(F1score)和标准化互信息(NMI)均好于比较算法。实验研究表明,所提算法具有较好的时间效率和准确度,适用于大规模网络社团划分。     

一个分层的BLOG社区识别算法

近年来,blog网站作为新型的网络媒体得到越来越多的个人和企业的关注。针对blog数据,提出了一种社区识别的算法。该算法认为具有相近兴趣、爱好的blogger会去阅读和评论类似的post,利用blog网站中各blogger对post的评论信息可以找出这些blogger因共同兴趣而形成的潜在社区。该算法分层识别blog空间中的社区,形成社区的层次结构。实验结果显示该算法是可行且有效的。     

微博社交网络社区发现方法研究

基于分析微博社交网络用户之间关系,提出了一种适用于微博的社区发现方法。实验表明这种方法能够有效地发掘微博社交网络中的社区结构。     

SSDBA: the stretch shrink distance based algorithm for link prediction in social networks

In the field of social network analysis,Link Predic-tion is one of the hottest topics which has been attracted attentions in academia and industry.So far,literatures for solving link prediction can be roughly divided into two categories:similarity-based and learning-based methods.The learning-based methods have higher accuracy,but their time complexities are too high for complex networks.However,the similarity-based methods have the advantage of low time consumption,so improving their accuracy becomes a key issue.In this paper,we employ community structures of social networks to improve the prediction accuracy and propose the stretch shrink distance based algorithm(SSDBA),In SSDBA,we first detect communities of a social network and identify active nodes based on community average threshold(CAT)and node average threshold(NAT)in each community.Second,we propose the stretch shrink distance(SSD)model to iteratively calculate the changes of distances between active nodes and their local neighbors.Finally,we make predictions when these links'distances tend to converge.Furthermore,extensive parameters learning have been carried out in experiments.We compare our SSDBA with other popular approaches.Experimental results validate the effectiveness and efficiency of proposed algorithm.     

基于“次中心”的社区结构探寻算法

当前社区结构探测算法在寻求社区结构划分正确性的同时,算法效率较低。为此,提出一种在算法正确性和算法效率两个方面能取得较好均衡的社区结构探寻算法CoreScan。该算法寻找节点集合中一类称之为“次中心”的特殊节点,再将其作为聚类中心,然后通过D模块度来发现社区结构。理论分析表明,该算法能正确识别Fortunato提出的一类特殊社区结构,且算法效率可达O(n*kmax),其中n是节点数量,kmax是“次中心”最大数量。最后通过多项实验证明,CoreScan算法能够在效率和正确性上取得较好的均衡,适合于在大规模节点集合中进行快速社区结构探寻。     

模块度增量与局部模块度引导下的社区发现算法

社区结构是复杂网络的重要特性之一,基于层次聚类的社区发现算法很好地利用了模块度来挖掘网络中的社区结构,但其局限性也导致算法对社区结构复杂的网络划分不够准确、无法发现小于一定规模的社区。在层次聚类的基础上,提出引入局部模块度来弥补模块度在划分社区时的不足,避免可能出现的划分不合理情况。通过真实数据集和人工网络进行了验证,实验结果证明,该算法具有可行性与有效性。