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

带有节点属性的网络社区发现算法综述 社区发现算法综述动态社区发现算法综述Chunaev P. Community detection in node-attributed social networks: a survey[J]. Computer Science Review, 2020, 37: 100286. 一、背景介绍 ??文章首先指出社区发现（community detection）是社交网络分析中的一个基本问题。一类经典的社区发现方法是仅处理网络的结构（即节点之间的联系），而忽略节点的特征。然而，大多数现实世界的社交网络提供了更多关于参与者的信息，而不仅仅是他们之间的联系。当存在参与者的信息时，网络被称为是有节点属性的（node-attributed）。另一类经典的社区发现方法是只使用节点属性来发现社区，完全忽略参与者之间的联系，代表方法有k-means聚类算法。显然，只处理结构或只处理属性的方法不能够完全利用网络中所有的可用信息。因此，研究能同时利用结构和属性的社区发现方法成为社会网络分析的一个新领域。??其次，文章提到了在过去的十年中，该领域出现了许多基于不同的思想和技术的方法。文章的目的是描述和阐明该领域的总体情况。此外，文章还提出了一种基于何时以及如何使用和融合网络结构和属性的分类方法，并给出了每个类的描述以及每个方法背后的一般技术思想。进一步地，文章还关注哪些方法优于其他方法，以及使用哪些数据集和质量度量来评估它们的性能。根据收集到的信息，作者总结了该领域的现状，并揭示了几个在未来需要解决的重要问题。 二、带有节点属性社交网络的社区发现问题及网络结构与属性融合的影响 1.社区发现问题陈述 ??图1展示了一个带有节点属性的网络。在该网络中进行社区发现需要实现了以下两个属性之间的某种平衡：（1）结构上的紧密性（structural closeness），即一个社区内的节点在结构上彼此接近，而不同社区的节点在结构上不接近；（2）属性上的同质性（attribute homogeneity），即一个社区内的节点具有同质属性，而不同社区的节点没有。 2.结构紧密性和属性同质性，结构与属性融合的效果 ??什么是结构紧密型呢？结构紧密性的要求是基于社交网络中的社区的概念。例如在Girvan and Newman (2002)中，社区被认为是节点的子集，子集内部连接紧密，子集之间连接稀疏。一个常见的度量方法是Newman’s Modularity。实际上，每个社区发现方法中结构紧密性的确切含义是由所选择的度量方法决定的。??什么是属性同质性呢？属性同质性要求是基于节点的特征能够反映和影响社交网络中的社区结构的社会科学基础。常见的社交网络中的同质性原则是志趣相投的节点更有可能被联系起来。属性同质性通常用Entropy来衡量。??接下来文章讨论了结构和属性融合的效果的不同观点。一方面，多个实验和许多论文表明网络的结构和属性往往提供互补的信息，能够提高社区发现质量。另一方面，一些实验表明，这并不总是正确的，网络结构和属性可能是正交的，相互矛盾的，从而导致社区发现结果不明确。文章认为对于融合结构和属性的效果以及这种融合如何影响社区发现的质量，目前还没有广泛接受的观点。关于结构和属性的融合何时对社区发现有价值以及何时没有价值的理论研究似乎是一件极其重要的事情。 三、相关工作及相关文献的整理 ??作者在这一章总结了之前关于社区发现综述的文章存在的问题，并介绍了他们关于相关文献有哪些信誉好的足球投注网站的过程以及方法和数据集的引用格式。此外，作者还提出了三点note：（1）本次调查不考虑多层网络（multi-layer networks）的社区发现方法；（2）本次调查主要考虑利用全属性空间寻找覆盖整个网络的社区的方法，不考虑探索属性的子空间和处理初始图的子图的方法；（3）本次调查不考虑文献网络聚类方法。 四、对与带有节点属性的社交网络的社区发现方法分类 ??作者根据社区发现过程中的结构和属性何时融合来对方法进行分类。如图2所示，将其分为了三类，分别是：（1）早期融合方法（early fusion methods），即在社区发现过程之前融合结构和属性；（2）同时融合方法（simultaneous fusion methods），即在社区发现的同时融合结构和属性；（3）后期融合方法（late fusion methods），即首先分别对结构和属性进行分区，然后进一步融合获得的分区。并且在第6-8章针对上述三个分类对其使用的社区发现算法、输入以及输出的社区类型（是否重叠）、数据集以及评估方法等方面进行了简要介绍。 五、最常用的带有节点属性的网络数据集和社区发现评估的质量度量 1.数据集 ??作者收集并简要描述了该领域常用的数据集，包含社交网络数据集（例如 Fac