基于遗传算法的复杂网络社区探测是当前的研究热点.针对该问题,本文在分析网络模块性函数Q的局部单调性的基础上,给出一种快速、有效的局部搜索变异策略,同时为兼顾初始种群的精度和多样性以达到进一步提高搜索效率的目的,采用了标签传...基于遗传算法的复杂网络社区探测是当前的研究热点.针对该问题,本文在分析网络模块性函数Q的局部单调性的基础上,给出一种快速、有效的局部搜索变异策略,同时为兼顾初始种群的精度和多样性以达到进一步提高搜索效率的目的,采用了标签传播作为初始种群的产生方法;综上,提出了一个结合局部搜索的遗传算法(Genetic algorithm with local search,LGA).在基准网络及大规模复杂网络上对LGA进行测试,并与当前具有代表性的社区探测算法进行比较,实验结果表明了文中算法的有效性与高效性.展开更多
提出一种新的面向复杂网络大数据的重叠社区检测算法DOC(detecting overlapping communities over complex network big data),时间复杂度为O(nlog2(n)),算法基于模块度聚类和图计算思想,应用新的节点和边的更新方法,利用平衡二叉树对...提出一种新的面向复杂网络大数据的重叠社区检测算法DOC(detecting overlapping communities over complex network big data),时间复杂度为O(nlog2(n)),算法基于模块度聚类和图计算思想,应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法.相对于传统的重叠节点检测算法,对每个节点分析的频率大为降低,可以在较低的算法运行时间下获得较高的识别准确率.复杂网络大数据集上的算法测试结果表明:DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法.展开更多
In this paper, we propose a balanced multi-label propagation algorithm （BMLPA） for overlapping community detection in social networks. As well as its fast speed, another important advantage of our method is good sta...In this paper, we propose a balanced multi-label propagation algorithm （BMLPA） for overlapping community detection in social networks. As well as its fast speed, another important advantage of our method is good stability, which other multi-label propagation algorithms, such as COPRA, lack. In BMLPA, we propose a new update strategy, which requires that community identifiers of one vertex should have balanced belonging coefficients. The advantage of this strategy is that it allows vertices to belong to any number of communities without a global limit on the largest number of community memberships, which is needed for COPRA. Also, we propose a fast method to generate ＂rough cores＂, which can be used to initialize labels for multi-label propagation algorithms, and are able to improve the quality and stability of results. Experimental results on synthetic and real social networks show that BMLPA is very efficient and effective for uncovering overlapping communities.展开更多
重叠社区发现是近年来复杂网络领域的研究热点之一.提出一种半监督的局部扩展式重叠社区发现方法SLEM(semi-supervised local expansion method).该方法借鉴了带约束的半监督聚类的思想,不仅利用网络的拓扑结构信息,还充分地利用网络节...重叠社区发现是近年来复杂网络领域的研究热点之一.提出一种半监督的局部扩展式重叠社区发现方法SLEM(semi-supervised local expansion method).该方法借鉴了带约束的半监督聚类的思想,不仅利用网络的拓扑结构信息,还充分地利用网络节点的属性信息.首先将网络节点的属性信息转化为成对约束,并根据成对约束修正网络的拓扑结构,使网络中的社区结构更加明显;然后基于网络节点的度中心性选取种子节点,得到分散的、局部节点度大的种子作为初始社区;再采用贪心策略将初始社区向邻居节点扩展,得到局部连接紧密的社区;最后检测并合并冗余社区,得到高覆盖率的社区发现结果.在模拟网络数据和真实网络数据上与当前有代表性的基于局部扩展的重叠社区发现算法进行了对比实验,结果表明SLEM方法在稀疏程度不同的网络上均能发现较高质量的重叠社区结构.展开更多
文摘基于遗传算法的复杂网络社区探测是当前的研究热点.针对该问题,本文在分析网络模块性函数Q的局部单调性的基础上,给出一种快速、有效的局部搜索变异策略,同时为兼顾初始种群的精度和多样性以达到进一步提高搜索效率的目的,采用了标签传播作为初始种群的产生方法;综上,提出了一个结合局部搜索的遗传算法(Genetic algorithm with local search,LGA).在基准网络及大规模复杂网络上对LGA进行测试,并与当前具有代表性的社区探测算法进行比较,实验结果表明了文中算法的有效性与高效性.
文摘提出一种新的面向复杂网络大数据的重叠社区检测算法DOC(detecting overlapping communities over complex network big data),时间复杂度为O(nlog2(n)),算法基于模块度聚类和图计算思想,应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法.相对于传统的重叠节点检测算法,对每个节点分析的频率大为降低,可以在较低的算法运行时间下获得较高的识别准确率.复杂网络大数据集上的算法测试结果表明:DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法.
基金supported by the Fundamental Research Funds for the Central Universities of Chinathe National Natural Science Foundation of China under Grant No. 60905029the Natural Science Foundation of Beijing of China under Grant No. 4112046
文摘In this paper, we propose a balanced multi-label propagation algorithm （BMLPA） for overlapping community detection in social networks. As well as its fast speed, another important advantage of our method is good stability, which other multi-label propagation algorithms, such as COPRA, lack. In BMLPA, we propose a new update strategy, which requires that community identifiers of one vertex should have balanced belonging coefficients. The advantage of this strategy is that it allows vertices to belong to any number of communities without a global limit on the largest number of community memberships, which is needed for COPRA. Also, we propose a fast method to generate ＂rough cores＂, which can be used to initialize labels for multi-label propagation algorithms, and are able to improve the quality and stability of results. Experimental results on synthetic and real social networks show that BMLPA is very efficient and effective for uncovering overlapping communities.
文摘重叠社区发现是近年来复杂网络领域的研究热点之一.提出一种半监督的局部扩展式重叠社区发现方法SLEM(semi-supervised local expansion method).该方法借鉴了带约束的半监督聚类的思想,不仅利用网络的拓扑结构信息,还充分地利用网络节点的属性信息.首先将网络节点的属性信息转化为成对约束,并根据成对约束修正网络的拓扑结构,使网络中的社区结构更加明显;然后基于网络节点的度中心性选取种子节点,得到分散的、局部节点度大的种子作为初始社区;再采用贪心策略将初始社区向邻居节点扩展,得到局部连接紧密的社区;最后检测并合并冗余社区,得到高覆盖率的社区发现结果.在模拟网络数据和真实网络数据上与当前有代表性的基于局部扩展的重叠社区发现算法进行了对比实验,结果表明SLEM方法在稀疏程度不同的网络上均能发现较高质量的重叠社区结构.
