多智能体系构架下的属性图分布式聚类算法

Distributed and Heterogeneous Multi-agent System for Attributed Graph Clustering

近年来属性图聚类受到了广泛关注,其目的是将属性图中的节点划分到若干簇中,使得每一个集群都有紧密的簇内结构和均匀的属性值。现有的理论主要是假设属性图中的节点或对象是为了协助优化某个给定的方程,而忽略了它们在现实生活中本身的属性。同时,一些开放性问题尚未得到有效解决,如异构信息集成、计算成本高等。为此,把属性图聚类问题理解为自身节点代理的集群形成博弈。为了有效地整合拓扑结构和属性信息,提出了基于紧密性和均匀性约束的节点代理策略选择。进一步证明了博弈过程将会收敛到弱帕累托纳什均衡。在实证方面,设计了一个分布式和异构的多智能体系统,给出了一个快速的分布式学习算法。该算法的主要特点是结果分区的重叠率可以由一个事先给定的阈值控制。最后,在现实社交网络上进行了模拟实验,并与目前先进方法进行比较,结果证实了所提算法的有效性。

Recent years have witnessed a renewed attention towards attributed graph clustering,which aims to divide the nodes in the attribute graph into several clusters,so that each cluster has a densely connected intra-cluster structure and homogeneous attribute values.Existing methods ignore nodes/objects selfish nature in real-life contexts.Meanwhile,some open problems,such as heterogeneous information integration,high computational cost,etc.,have not been effectively resolved yet.To this end,we considered the attribute graph clustering problem as the cluster formation game of selfish node-agents.To effectively integrate both topological and attributive information,we proposed both tightness and homogeneity constraints on node-agents' strategy selection.To be specific,the game process will converge to weakly Pareto-Nash equilibrium almost surely.In the aspect of implement,we carefully designed a distributed and heterogeneous multiagent system,based on which,a fast distributed learning algorithm is also given.The main feature of the proposed algorithm is that the overlap rate of the resulted partition can be well controlled by apre-specified threshold.Finally,we conducted a set of simulation experiments on real-life social networks and comparisons are listed.