＜论文＞A graph clustering method for community detection in complex networks重点摘要
Introduction
许多现有的方法主要关注于拓扑特征及其相似性。在图聚类任务中，核心目标在于识别具有高度内聚性的子图网络，并整合分析这两个高度相关的子集群。
1.同一子图中的顶点应具有高内聚性，但与其他子图的连接应稀疏。
2.相似的顶点应被分到同一组，而不相似的顶点应保持在不同的组中。
图聚类技术通常不是仅关注网络的拓扑结构就是仅仅关注节点属性。因此，在多数情况下很难找到一种方法能够综合分析这两者。
AR-Cluster通过识别具有结构与属性相似性的节点，在低计算成本下完成图聚类过程。相较于其他相关方法而言，AR-Cluster具有以下两个显著特点：第一点是采用了基于节点吸引力与推荐值的新颖配对式结构相似性测度方法；第二点是引入了一种基于最大推荐值的新颖路径选择策略。
论文贡献：1. 本文开发出一种新的指标体系；2. 开发出一种创新性地结合了节点间相似性与图结构特性的相似性计算方法；3. 构建了一种综合考虑了节点之间的拓扑关系及其属性信息的图聚类算法。
Related works
网络的拓扑结构揭示了节点间的关系，在此基础之上
AR-Cluster algorithm
Problem statement
为实现图聚类任务需关注的两大要点是：第一，在每个子图内部的所有节点间应当具有较高的凝聚力，并且与其它子图之间保持稀疏连接；第二，在同一类别内的节点应当被划分为同一个群体内，则在不同类别间的节点则被分配到不同的群体内。该算法包含两大核心要素：一是相似度计算机制；二是聚类策略设计。本研究将重点探讨这两个关键要素的实现过程及性能表现
在构建图聚类方法时需关注的两个主要方面是：其一是确保子图内部节点之间具有紧密相连的关系，并与其它独立的子图保持弱连接关系；其二是将具有相同性质的节点归为同一簇，并将不同性质的节点则各自占据独立的簇。我们的算法架构主要围绕解决两大核心问题展开，在具体实现过程中需要综合考虑相似度量化测以及相应的聚类策略设计，在接下来的内容中我们将重点阐述这两个关键模块的具体实现方案
Attracting and recommending degrees（吸引度与推荐度）
通常而言，一个图由其拓扑结构以及顶点属性两部分构成。两者均具有重要意义，在当前研究中仍面临诸多挑战。大部分现有方法仅关注其中一项特性，在这种情况下难以满足复杂场景的需求。为此，我们开发了一种称为 AR-Cluster 的新型图聚类技术。该技术主要依据吸引力指标与推荐性评估来实现分类
在实际应用背景下，图论被广泛应用于复杂网络的建模研究。两个顶点之间若存在直接连接，则反映了它们之间的亲密度；而紧密的关系则表现出较高的吸引力。此外，在不同源节点间通过路径相连的信息传递过程具有重要的传播特性。基于以上关键特征分析，在此基础上构建了一种新的聚类方法。
在无向属性图中直接相连的一对顶点之间所体现出的亲密关系我们称之为吸引因子
和
分别是点
和点
的度。连接
和
之间的单个无向链接的权重为
。
和
之间的吸引因子
定义如公式（1）所示。
定义2（吸引度） ：
与
为无向加权图中的一对直接连接的顶点。
和
之间的吸引度
定义为：
该指标被称为吸引因子，并且能够直接识别出哪个顶点更为重要；同时还可以推断出连接这两个顶点的吸引力关系。
，这是因为它们的权重和度数不同。
不满足对称性，但是
满足。
其对应的边权值存在显著差异；这表明，在这种网络拓扑结构下（基于公式1），连接节点之间的吸引力呈现出明显的层次性分布特征；参考图1可知, 该图为一个非平凡的加权多属性网络模型；具体而言, 每个节点均取两个维度的信息: 工作与体育爱好. 相应地, 吸引力及其表现形式可在表2与表3中得到详细描述.
段落保持不变
到另一个目标顶点
的路径是一系列具有重要引导作用的边
，其中
我们称这种传递信息为推荐信息。这种推荐信息逐渐积累直至抵达目标终点。
定义3（推荐度） ：给定从一个源顶点
到一个目标顶点
的路径
，其中
，则从
到
的推荐度
定义如下（见公式3）：
这里的
是在直接连接下的吸引因子。
在属性图中，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况
Structural and attribute similarities（结构和属性相似性）
杰卡德相似系数用作基本的结构相似性度量。
该方法在发现对象间的关联方面应用广泛。
该方法通过分析图的拓扑结构来识别其关键特征——带有权重联系的核心节点。
因此, 该方法采用了固定Jaccard相似ity系数作为基础来构建其新的相似度量。
该方法适用于多种类型的网络数据模型。
其中所有顶点之间的关联关系分为三种类型: 直接相连、间接通路以及完全断开的状态。
参考公式5和6, 在直接相连的情况下采用一种计算方式, 在间接通路的情况下采用另一种计算策略。
在公式（6）中，
基于一对直接相连的顶点之间的结构相似性。在源节点到目标节点之间可能存在多条路径。IGC-CSM采用加权最短路径而非全部路径。由此可知，在间接相连的一对顶点中，其结构相似度数值通过直接相连顶点的结构相似度数值进行线性乘积计算。
在获得了顶点吸引力评分及传播影响力评分后（我们能够通过），能够通过借鉴IGC-CSM方法的核心理念（所提出的方法同样采用了协同性评估机制），计算各顶点间的相互关联程度（这使得）这一指标成为衡量网络结构的重要工具。
在公式（7）中，
表示两个顶点
和
我们关注的是节点间的结构相似性。具体而言，我们采用三种不同的连接模式来计算节点间的相似性。（a）对于直接相连的一对节点，则综合考虑其吸引力与固定不变的Jaccard Similarity系数来评估其结构相近程度。（b）对于通过中间节点间接相连的一对节点，则基于其直接邻居间的关系强度以及各自影响力因子的最大乘积关系来进行估算。（c）若两节点之间处于完全断开状态，则认定它们之间的关系强度为零。
在加权属性图中进行相似度计算时需要综合考虑所有节点的属性特征每个节点都可承载多种属性维度这些维度可能代表不同的信息或关系当这些节点处于不同语义环境中其重要性变得明显因此建议着重评估属性间的相似程度以提升节点内部的凝聚性一个节点可能包含多个关联属性每个关联属性又包含多个具体值为保证分析的一致性我们对每个节点设定相同数量的属性指标例如我们为每个顶点定义了两个核心指标如图1所示这两个指标均包含四个子项每个指标的权重设定为1为了衡量这些指标间的相似程度我们采用了IGC-CSM方法具体的计算公式如下所示其中
表示属性权重。
在涉及方程式（8）及方程式（9）的过程中，在算法启动阶段被初始化了所有参数。综合考虑的最终相似性指标则通过等式（10）得以体现。
参数
这是一个调节参数被用来控制网络连通性与意义相关联的因素。该方法具有一定的易用性，在应用该方法之前需预先设定相关参数。最佳设置是指将网络划分为k个具有高内聚性和属性均匀性的簇。
Algorithm description
为了计算最终的相似性指标，在完成对各节点间关系评估的基础上
在算法运行初期阶段，我们选取度值最高的k个顶点来设定为初始中心节点。在每一次循环过程中，上述设定的中心节点位置会发生调整，并依据最短距离原则将未被归类的所有顶点分配至最近的那个中心节点。具体而言，AR-Cluster算法的工作流程如下所述。
附
该算法以距离为评估标准，并将数据划分为若干个簇（clusters）。其本质上是一种变体，在每个簇中都选取一个medoid数据点来代表整个簇的数据特征。与k-means方法不同，在k-medoids算法中，并不选择簇内数据的平均值作为中心点；相反地，它会选择一个真实存在的数据点作为medoid。这种机制使得k-medoids对于异常值具有更强的鲁棒性。
K-Medoids的核心理念在于，在聚类过程中确定适当的中心点位置，并将剩余的数据对象归并到离它最近的那个簇的核心位置。在每一次迭代阶段，如果有必要的话就可以更换当前的中心点配置直至达到稳定状态。
总体而言，K-Medoids是一种基于距离度量的聚类算法，在确定数据簇中心时使用真实数据点作为代表，并表现出一定程度的抗噪声能力。