Graph is a universal model to describe real world complex systems,and large graph datasets are common in many application domains.Graph clustering techniques are critical for understanding,analyzing as well as visualizing large graphs.However,with the proliferation of rich attribute information available for objects in real-world graphs,how to leverage structure and attribute information for clustering attributed graphs becomes a new challenge.Most of the existing methods either take traditional clustering approaches by converting structure and attribute information into distance,or just consider one of the two aspects.In this paper,we propose a novel attributed graph clustering method GA-AGC,based on genetic algorithm and Minimum Description Length (MDL).By analyzing the problem of attributed graph clustering,we convert it to the category of Minimum Description Length.The genetic algorithm solution adopts an extended label propagation method as its initialization procedure,and combines a local mutation operator with decreasing description length.The algorithm proposed requires no specified number of clusters,and its running time scales linearly with total number of graph nodes and edges.Extensive experiments on real-life datasets prove the effectiveness and efficiency of our proposed method.%图是描述现实世界各类复杂系统的一种普适模型,且许多实际应用中的图是大规模的.图的聚类是理解、分析和可视化大规模图的关键技术之一.现实世界的图往往包含丰富的属性信息,如何综合结构和属性信息进行属性图的聚类是一个新的挑战.大多数的现有方法或者将结构和属性转化为距离,基于传统方法进行聚类;或者只考虑某一方面聚类.文中结合信息论中最小长度原则,基于遗传算法,提出一种高效的属性图聚类方法GA-AGC.通过对属性图聚类问题建模,转化为最小描述长度原则问题;扩展标签传播方法作为遗传算法初始化方法,结合编码减小的局部变异方法,提出一种解决属性图聚类的遗传算法.文中方法无需设定聚类的数目,算法复杂度近似线性于结点和边的数目.真实数据集上的实验验证了算法的有效性和高效性.
展开▼
