一种有向网络中社团结构划分的启发式算法  

A Heuristic Algorithm for Partitioning Community Structures in Directed Network

作　　者：李锋[1] 

机构地区：[1]华南理工大学工商管理学院,广州510640

出　　处：《系统管理学报》2014年第4期495-500,共6页Journal of Systems & Management

基　　金：国家自然科学基金资助项目(71171085;71101063);华南理工大学中央高校基本科研业务费专项基金资助项目(2014ZZ0074)

摘　　要：复杂网络中的社团发现和探测是当前复杂网络分析领域中的一个热点研究问题,并且具有非常广泛的应用前景。但是,传统的社团划分算法主要以无向、无权网络为对象进行分析,不能够适用于现实世界中更多的有向网络、赋权网络等。以有向网络为研究对象,研究其中的社团划分算法。鉴于前人提出的有向网络中社团划分算法存在着计算时间复杂度问题,引入模拟退火算法对其进行改进,并在改进算法中考虑了节点的网络结构属性。通过对不同规模的计算机生成的有向网络进行算法测试,验证了本文算法的正确性。最后,对一个实际复杂网络进行了社团划分,进一步验证了算法的有效性。The problem of detecting or finding community structure in large-scale directed networks is increasingly attracting research attention because of its practical and theoretical values and its potential applications.However,this problem is rather complicated when the network is directed and weighted.The previous research mainly focuses on detecting community structure in undirected network.This paper addresses this problem,namely,finding community structure in directed networks.A simulated annealing algorithm is introduced to improve the algorithm proposed by Leicht and Newman.Moreover,the structural characteristic of each node is also considered in the algorithm.The algorithm was verified by several test networks with both computer-generated and real directed networks.

关 键 词：社团结构 有向网络 社团发现算法 启发式算法 模拟退火算法 

分 类 号：F181[经济管理—世界经济]