基于多节点社团意识系统的属性图聚类算法

摘要

属性图用属性向量描述节点,用边描述节点间的关系。为了把节点划分为具有紧密联系的社团,一种有效的方法是对属性图进行聚类。聚类方法有不同的标准,如节点连接度和属性相似度。虽然社团一般是围绕紧密的连边和相似的属性值的节点形成,但是目前的方法都只关注了这两种数据形式中的一种。通过给每个节点赋予一个自治域,提出一个准确且可延展的多节点系统用于提取属性图中的重叠社团。首先,引入带有可调带宽因子的核函数用于测度每个节点的影响力,具有最高局部影响力的节点可以被看作领导节点。其次,提出一种新颖的局部扩展策略,使每一个领导节点能够吸收属性图中相关性最强的跟随者。接着,设计了多节点社团意识系统,该系统为节点之间的充分沟通提供了必要的条件,从而能够得出最优的重叠社团结构。社团中的节点不仅互相联系紧密,而且也有相似的属性。该算法的计算复杂度在特定带宽条件下近似于连边数目的线性函数。最后,基于标准属性图和真实属性图的实验验证了该系统的有效性和高效性。