带有节点属性的网络社区发现算法综述

带有节点属性的网络社区发现算法综述社区发现算法综述动态社区发现算法综述ChunaevP.Communitydetectioninnode-attributedsocialnetworks:asurvey[J].ComputerScienceReview,2020,37:100286.一、背景介绍  文章首先指出社区发现（communitydetection）是社交网络分析中的一个基本问题。一类经典的社区发现方法是仅处理网络的结构（即节点之间的联系），而忽略节点的特征。然而，大多数现实世界的社交网络提供了更多关于参与者的信息，而不仅仅是他们之间的联系。当存在参与者的信息时，网络被称为是有节点属性的（node-attributed）。另一类经典的社区发现方法是只使用节点属性来发现社区，完全忽略参与者之间的联系，代表方法有k-means聚类算法。显然，只处理结构或只处理属性的方法不能够完全利用网络中所有的可用信息。因此，研究能同时利用结构和属性的社区发现方法成为社会网络分析的一个新领域。  其次，文章提到了在过去的十年中，该领域出现了许多基于不同的思想和技术的方法。文章的目的是描述和阐明该领域的总体情况。此外，文章还提出了一种基于何时以及如何使用和融合网络结构和属性的分类方法，并给出了每个类的描述以及每个方法背后的一般技术思想。进一步地，文章还关注哪些方法优于其他方法，以及使用哪些数据集和质量度量来评估它们的性能。根据收集到的信息，作者总结了该领域的现状，并揭示了几个在未来需要解决的重要问题。二、带有节点属性社交网络的社区发现问题及网络结构与属性融合的影响1.社区发现问题陈述  图1展示了一个带有节点属性的网络。在该网络中进行社区发现需要实现了以下两个属性之间的某种平衡：（1）结构上的紧密性（structuralcloseness），即一个社区内的节点在结构上彼此接近，而不同社区的节点在结构上不接近；（2）属性上的同质性（attributehomogeneity），即一个社区内的节点具有同质属性，而不同社区的节点没有。2.结构紧密性和属性同质性，结构与属性融合的效果  什么是结构紧密型呢？结构紧密性的要求是基于社交网络中的社区的概念。例如在GirvanandNewman(2002)中，社区被认为是节点的子集，子集内部连接紧密，子集之间连接稀疏。一个常见的度量方法是Newman’sModularity。实际上，每个社区发现方法中结构紧密性的确切含义是由所选择的度量方法决定的。  什么是属性同质性呢？属性同质性要求是基于节点的特征能够反映和影响社交网络中的社区结构的社会科学基础。常见的社交网络中的同质性原则是志趣相投的节点更有可能被联系起来。属性同质性通常用Entropy来衡量。  接下来文章讨论了结构和属性融合的效果的不同观点。一方面，多个实验和许多论文表明网络的结构和属性往往提供互补的信息，能够提高社区发现质量。另一方面，一些实验表明，这并不总是正确的，网络结构和属性可能是正交的，相互矛盾的，从而导致社区发现结果不明确。文章认为对于融合结构和属性的效果以及这种融合如何影响社区发现的质量，目前还没有广泛接受的观点。关于结构和属性的融合何时对社区发现有价值以及何时没有价值的理论研究似乎是一件极其重要的事情。三、相关工作及相关文献的整理  作者在这一章总结了之前关于社区发现综述的文章存在的问题，并介绍了他们关于相关文献搜索的过程以及方法和数据集的引用格式。此外，作者还提出了三点note：（1）本次调查不考虑多层网络（multi-layernetworks）的社区发现方法；（2）本次调查主要考虑利用全属性空间寻找覆盖整个网络的社区的方法，不考虑探索属性的子空间和处理初始图的子图的方法；（3）本次调查不考虑文献网络聚类方法。四、对与带有节点属性的社交网络的社区发现方法分类  作者根据社区发现过程中的结构和属性何时融合来对方法进行分类。如图2所示，将其分为了三类，分别是：（1）早期融合方法（earlyfusionmethods），即在社区发现过程之前融合结构和属性；（2）同时融合方法（simultaneousfusionmethods），即在社区发现的同时融合结构和属性；（3）后期融合方法（latefusionmethods），即首先分别对结构和属性进行分区，然后进一步融合获得的分区。并且在第6-8章针对上述三个分类对其使用的社区发现算法、输入以及输出的社区类型（是否重叠）、数据集以及评估方法等方面进行了简要介绍。五、最常用的带有节点属性的网络数据集和社区发现评估的质量度量1.数据集  作者收集并简要描述了该领域常用的数据集，包含社交网络数据集（例如Facebook、LastFM和Twitter），引文网络数据集（例如DBLP、Wiki和专利）等。为了方便起见，作者按照数据集中节点的多少进行区分，划分为了表1小型数据集（<），表2中型数据集（），表3大型数据集（>）。2.评估方法  对于网络社区发现的结果，需要评估它们的质量。根据所使用的数据集，可以分为两种情况。如果该数据集没有真实的社区，则可以使用各种结构接近度和属性同质性的度量，例如，模块度、密度、传导性、持久性、簇内和簇间密度等。如果存在真实社区情况，可以通过以下常用的度量方法来将检测到的社区与真实情况进行比较。例如：准确度、归一化互信息（NMI）、调整后的兰德指数（ARI）或兰德指数（RI）和F度量。六、早期融合方法（Earlyfusionmethods）1.基于权重的方法（Weight-basedmethods）  这些方法（具体可见文中表4和表5）将属性转换为加权属性图，并以某种方式将其与结构图合并。结果得到一个加权图，它代替了节点属性图，如图3所示。的边权通常分配如下：其中和分别代表结构相似函数和属性相似函数，超参数控制结构和属性之间的平衡。  一旦构建了加权图，就可以在其上使用经典的图聚类算法，例如WeightedLouvain。有时，会被转换成一定的距离矩阵，通过基于距离的聚类算法（如k-means或k-medoids）进一步用于发现社区。  调试通常是人工执行的。相似函数和的选择通常是由特定方法的作者的偏好决定的。对于这种选择如何影响社区发现结果的系统研究尚待进行。2.基于距离的方法（Distance-basedmethods）  前一小节中讨论的方法旨在以统一的图形式表示结构和属性，以便于进一步的图聚类。相反，基于距离的方法（具体可见文中表6）有意地放弃图的表示，而采用包含结构和属性信息的距离矩阵表示。距离矩阵通常是通过结构和属性感知的距离函数融合组件得到的，如图4所示。矩阵可通过基于距离的聚类算法（如k-means和k-medoids）进一步用于发现社区。融合结构与属性的距离函数通常是如下形式：其中和分别是结构和属性距离函数。和(6.1)相同，(6.2)中的控制各组分之间的平衡，如何恰当地选择它似乎也是一个悬而未决的问题3.基于节点增广图的方法（Node-augmentedgraph-basedmethods）  本小节的方法（具体可见文中表7）将初始节点属性图G转换为另一个节点增广图，其中节点来自V和新的代表属性的属性节点，如图5所示。然后进一步在上进行社区发现。  注意，上述的增广并不适用于连续属性。特别是当属性维度和属性的取值很多时，这种方法计算起来相当昂贵。4.基于嵌入的方法（Embedding-basedmethods）  众所周知，图作为网络的传统表示形式给网络分析带来了一些困难。新的嵌入技术旨在通过学习节点嵌入来解决这一问题，即网络节点的低维连续向量表示，从而有效地编码主网络信息。粗略地说，节点嵌入技术允许将一个有n个节点的图转换成一个有n个向量的集合。有了节点嵌入（即向量），就可以使用经典的基于距离的聚类算法，如k-means，来检测社区，见图6。具体可见文中表8列举的方法。5.基于模式挖掘（早期融合）方法（Patternmining-based(earlyfusion)methods）  Motif被认为是复杂网络的构建模块。我们发现使用这种模式对节点属性社交网络进行社区发现的方法只有一种，即AHMotif(Lietal.,2018)，见文中表9。该方法根据motif中涉及的节点属性，为网络中识别的结构motif配备所谓的同质性值。该信息存储在一个特殊的邻接矩阵中，该矩阵可以作为经典社区发现算法的输入。七、同时融合方法（Simultaneousfusionmethods）  同时融合方法在社区发现的过程中同时融合结构和属性。由于这个原因，这些方法通常需要特殊的社区发现方法来实现，而早期和晚期的融合方法在一定程度上允许使用经典社区发现算法来实现。1.改进经典聚类算法的目标函数的方法（Methodsmodifyingobjectivefunctionsofclassicalclusteringalgorithms）  文章中的表10包含了同时融合方法的简短描述，这些方法修改了常用的聚类算法的目标函数，如Louvain、NormalizedCut、k-means、k-medoids和kNN。他们的主要想法是采用经典的方法在优化过程中同时使用结构和属性。2.基于元启发式的方法（Metaheuristic-basedmethods）  这类方法在思想上与第7.1节中的方法相似。然而，他们并没有修改常用的社区发现算法的目标函数和迭代过程，而是直接应用元启发式算法以找到一个节点属性网络分区，为某些结构紧密度和属性同质性度量提供最优值。文中表11给出了这类方法的简短描述。3.基于非负矩阵分解和矩阵压缩的方法（Methodsbasedonnon-negativematrixfactorizationandmatrixcompression）  非负矩阵分解（non-negativematrixfactorization，NNMF）是一种矩阵分解技术，它是用秩较低的非负矩阵的乘积来近似高秩的非负矩阵，，从而使Frobenius范数的近似误差最小。众所周知，NNMF能够在输入数据中找到簇。要将NNMF应用于节点属性社交网络中的社区发现，需要对结构和属性进行适当的融合。有人提出了这种改编的不同版本，见文中表12。4.基于模式挖掘（同时融合）方法（Patternmining-based(simultaneousfusion)methods）  在节点属性社交网络中进行的模式挖掘主要是在网络结构和属性中提取特定属性子集或连接子集等模式。除此之外，这有助于理解网络并理解它是如何形成的。在社区发现的背景下，提取的模式被用作社区的构建块。相关方法见文中表13。5.基于概率模型的方法（Probabilisticmodel-basedmethods）  在假设网络结构和属性是根据选定的参数分布生成的情况下，该类方法从概率上推断节点属性社交网络中节点的社区成员分布。生成模型和判别模型主要用于推理。值得一提的是，正确选择结构和属性的先验分布是一项非常重要的任务。表14给出了这类方法的简短描述。6.基于动态系统和基于代理的方法（Dynamicalsystem-basedandagent-basedmethods）  该类方法（见文中表15）将节点属性社交网络视为一个动态系统，并假设其社区结构是节点之间某些交互的结果。有些方法假设交互发生在信息传播过程中，即当信息发送到或从每个节点接收时。其他方法将每个节点理解为一个自治的代理，并开发一个多代理系统来检测社区。需要注意的是，这些方法都是最近才出现的，从一个新的角度考虑了节点属性社交网络中的社区发现。此外，它们对于大型网络似乎是有效的，因为可以很容易地并行化。八、后期融合方法（Latefusionmethods）  后期融合方法旨在社区发现过程之后融合结构和属性信息。更准确地说，社区发现首先针对结构（例如Louvain）和属性（例如k-means）分别执行。之后，获得的分区以某种方式融合以获得结构和属性感知分区，如图7所示。后期融合方法通常允许研究人员/数据科学家使用经典社区发现和共识聚类算法的现有实现来获得所需的分区。1.基于共识的方法（Consensus-basedmethods）  给定一组分区，共识聚类算法的一般目标是找到一个单一的合并分区，该分区聚合集合中的信息。如果一个人有一组单独（甚至联合）的结构和属性分区，共识聚类背后的想法显然适用于节点属性社交网络中的社区发现。表16包含了应用该思想的方法的简短描述。2.基于替换的方法（Switch-basedmethods）  这类方法中包含的唯一方法（见文中表17）也是处理根据结构和属性分别获得的分区，但不同的是选择更可取的分区而不是寻找共识。即当结构分区不明确时，方法从基于结构的分区切换到基于属性的分区。九、整体情况分析  作者使用PageRank来寻找该领域最有影响力的方法。如图8所示，绿色越深表示该节点的PageRank越高。作者认为这些方法可能会被研究人员进一步研究。基于权重的SAC2和CODICIL基于节点增强图的SA-Cluster、Inc-Cluster和SA-Cluster-Opt修改Louvain目标函数的SAC1基于NNMF的SCI和基于矩阵压缩的PICS基于模式挖掘（同时融合）的DCM基于概率模型的PCL-DC、BAGC、GBAGC、CESNA和Circles  从图8中，可以看出网络是相当稀疏甚至是不连贯的。说明该领域的方法的比较研究还远未完成。接下来将从几个角度对方法评估问题进行讨论。（1）假设两种方法对许多数据集和度量显示相同的社区发现质量，提出应该考虑每种方法使用多少时间/空间。特别地，作者提出可以根据节点属性图中的顶点数、边数和属性维数来考虑方法的计算复杂度。但目前论文的作者经常省略对复杂度的估计。这使得无法在计算复杂度方面对各种方法进行整体比较。（2）作者使用不同的数据集和评估措施来测试他们的方法，因此无法对不同论文中的实验结果进行统一比较。并且很多论文没有提供源代码，使结果复现成为难题。（3）作者在文中讨论了具体的评估方法，并且按照有没有真实的社区结构，划分为了两种评估策略。并分别对两种评估策略目前的发展和存在的问题进行了阐述。十、结论  本文对带有节点属性的社交网络中的社区发现方法进行研究，简要描述了75种