属性网络中的社区发现：合成数据和现实世界的比较研究

跟踪：挖掘属性网络WWW 2018，2018年4月23日至27日，法国里昂1299属性网络中的社区发现摘要伊萨姆·法利赫Paris 13 UniversityVilletaneuse，FRANCEissam.lipn.univ-paris13.frRushedKanawatiParis 13UniversityVilletaneuse，FRANCErk@lipn.univ-paris13.frNistorGrozavuParis 13UniversityVilletaneuse，FRANCEnistor. lipn.univ-paris13.frYounès Bennani巴黎13大学Villetaneuse，法国younes. lipn.univ-paris13.fr顶点属性将作者的属性或特征描述为图聚类技术对于检测大型图中的密集连接组非常有用现有的许多图聚类方法主要关注图的拓扑结构，而忽略了图的顶点属性。现有的图聚类方法最近已经扩展到处理节点属性。首先，我们激发了对这一问题的研究兴趣。然后，我们回顾了提出来处理这个问题的主要方法。我们提出了一个比较研究的一些现有的属性网络社区检测算法的合成数据和现实世界的数据。CCS概念• 计算理论→无监督学习和聚类;社交网络;关键词属性网络;社会网络分析;群落检测;聚类ACM参考格式：Issam Falih、Nistor Grozavu、Rushed Kanawati和Younès Bennani。2018年。属性网络中的社区检测 在WWW '18伴侣：2018年网络会议伴侣，2018年4月23日至27日，法国里昂。ACM，New York，NY，USA，8页。https://doi.org/10.1145/3184558.31915701引言在许多应用中，真实世界的图形数据通常与附加信息相关联，即：图的顶点与描述该顶点的多个属性相关联。实际上，有两个数据源可用于执行社区检测任务。第一个是关于节点及其属性的数据，第二个数据源来自顶点之间的不同类型的连接。例如，在社交网络中，边属性表示人与人之间的关系（友谊、协作、家庭等），而顶点属性描述人的角色或个性。另一个示例是书目网络，顶点可以表示作者和作者。本文在知识共享署名4.0国际（CC BY 4.0）许可下发布作者保留在其个人和公司网站上以适当的归属方式传播作品的权利。WWW©2018 IW3C2（国际万维网会议委员会），在知识共享CC BY 4.0许可下发布。ACM ISBN 978-1-4503-5640-4/18/04。https://doi.org/10.1145/3184558.3191570感兴趣的领域，出版物的数量，而拓扑结构表示作者之间的关系。因此，重要的是要同时考虑两个信息源，并将网络社区视为密集连接的节点集，但也共享一些共同的属性。节点属性可以补充网络结构，导致更精确的社区检测;另外，如果一个信息源丢失或有噪声，则另一个将被利用。然而，考虑节点属性和网络拓扑用于社区检测也是具有挑战性的，因为该方法必须组合两种类型的信息[33]。最近，只有少数最近的研究解决了属性网络中的聚类问题[24];[4];[21]。该问题是基于如何调整拓扑信息和属性信息的贡献度而提出的。本文的主要贡献如下：我们将现有的处理属性聚类问题的方法我们比较了一组属性网络社区检测算法的合成数据和真实数据的集合。实验结果表明，结合这两种类型的信息的算法成功地组成有意义的簇的顶点为了探索这一任务，本文组织如下。首先，我们在第2节中介绍属性网络聚类问题。我们给出了一个现有的国家的最先进的方法，处理这个问题的分类。第三节对现有的一些属性网络社区发现算法进行了实验评估最后，第四部分对本文进行了总结。2属性网络聚类在许多应用中，拓扑信息以及属性数据可用于对象。这两种类型的信息都可以被建模为顶点标记图，使得顶点表示对象，边表示它们之间的关系，并且与顶点相关联的特征向量表示每个对象的属性信息。定义. 属性图G被定义为4元组（V，E，A，F），其中V={v1， v2，…v n}是n个顶点的集合，E={（u，v）：u，v∈|V|，u辛v}是边的集合，A={ai，a2，…a T}是T个属性的集合，F ={f1，f2，… f T}是T个属性函数的集合··跟踪：挖掘属性网络WWW 2018，2018年4月23日至27日，法国里昂1300≤ ≤ ∈VVAVV →V P{SGVA0t=1不0否则}并且每个函数f t：dom（a t）将属性a t的域dom（a t）中的属性值分配给每个顶点 （对于t：1tT）。在属性图G中，顶点v本质上与长度为T的属性向量相关联，其中向量中的元素t由函数ft（v）给出。表1给出了本文中使用的主要符号符号描述VAP（u，v）mdvfat（ v）顶点集V={vi：1≤i≤|V |}属性集合A={ai：1≤i≤|一|}分割，其中P={C1，C2，...，Ck}顶点u和顶点v网络中的边数顶点的度返回属性顶点v的值表1：属性网络：符号问题陈述。 1.定义一个图G（、E、、F）和聚类数k，聚类问题是划分混合方法：属性和拓扑信息被认为是分开的。例如，它可以通过仅使用拓扑方法和仅使用向量聚类方法来计算集群然后采用集成聚类方法对结果进行融合2.1基于拓扑的方法这类方法的基本思想是将属性网络聚类问题转化为拓扑聚类问题。节点它将用于改变输入图的初始拓扑结构接下来，我们提出了不同的方式来考虑节点2.1.1基于边缘加权的方法。为了在聚类过程中整合属性信息，这些方法定义了节点属性之间的相似性度量，该相似性度量将用于对现有边进行加权。节点之间的相似性通过检查它们共有的T个属性值中的每一个来确定。 然后可以应用加权图的任何无监督聚类算法。权重的值将影响聚类算法，以优先创建其中G的顶点集分成k个不相交子集=C1，C2，…，Ck，使得：(1) Ci ∩ Cj = i ≠ j且∪iCi = |V|节点不仅连接良好而且相似。算法1示出了该方法的主要轮廓。算法1基于边缘加权的方法(2) 簇内的顶点是密集连接的，而不同簇中的顶点是稀疏连接的。(3) 预期相同集群中的节点具有同质属性。向量数据的传统聚类评估聚类w.r.t.所有属性;它们不处理对象是通过像K均值那样的边彼此连接的节点的图形数据。另一方面，众所周知的图聚类技术，如基于归一化割的聚类[26]，模块化[23]使用网络的关系将图划分为几个密集连接的组件，但不使用节点的属性。问题是应用聚类方法，同时使用图形数据和属性数据，以检测在图形中密集连接的集群，并在同一时间使用属性空间中的相似性最近很少有研究解决了属性网络中的聚类问题属性网络中的社区检测识别簇或者在网络的整个空间中或者在多个子空间中要求：（，E，，F）：属性图。相似性函数。clustAlдow ：加权图的聚类算法。确保：V的分区。Gw=（V，E，w）;w：V×V →R对于（u，v）∈E（Gw）w（u，v）= S（f 1.. T（u），f 1.. T（v））端P=clustAl_o_w（G_w）返回P我们在下文中报告了采用这一战略的主要工作在[20]中，作者提出了匹配系数相似性函数，该函数包括对两个连接的顶点计算它们共有的属性值的数量。形式上，两个顶点（u，v）上的匹配系数由下式给出：[1][3]、[14][13]。在本文中，我们专注于在全空间的情况下，属性网络社区检测算法属性化网络社区S（u，v）=. . 不哪里sat（u，v）i f（u，v）∈E或（v，u）∈E否则（一）检测算法可以分为三个主要类别是一个 （u，v）=.1i f ft（u）=ft（v）基于拓扑的聚类：属性信息被用作附加的拓扑信息。实际上，可以使用属性信息以便改变输入图的初始拓扑。基于属性的聚类：拓扑信息是与顶点属性一起合并成全局相似性/距离，其然后可以由任何经典聚类算法处理。一旦权重改变，作者使用经典的无监督学习算法，如Karger也可以使用Louvain [2]处理加权图的社团检测算法最初，匹配系数相似性度量仅处理分类属性。它被[27]扩展到同时处理分类和连续属性。对于连续属性，首先将每个属性规范化为范围···根据其方法原则：跟踪：挖掘属性网络WWW 2018，2018年4月23日至27日，法国里昂1301∈1dvdu|×个|×GVA∈sat（ u，v）=0α t ft（ u）= ft（ v）否则ifa t连续通过添加表示为α的归一化参数，然后使用属性值对之间的算术差来获得相似性得分。该相似性度量表示为：接近度和属性相似度通过随机游走距离测量。然后，利用随机游走距离作为聚类过程中的两两相似性度量，通过K-Medoids聚类方法将图划分为k个簇。方法1i facatero ical&f（u）=f（v）基于增广图的方法只能处理分类属性’。1-|不|tt但它可以很容易地扩展到处理分类和对比。其中αt是对应于属性αt的归一化参数。它允许在[0， 1]的范围内规范化t基于边权值的方法根据节点属性的相似性产生新的如果原始图是加权的，则可以合并两个权重这一系列技术易于实现，但它们的缺点是它们仅考虑直接连接的顶点图中未直接连接的顶点具有等于零的相似性，而不管它们的属性值如何。2.1.2基于增强图的方法。这种方法试图通过一个增广图将拓扑结构和属性信息结合起来。原始图的初始拓扑结构被新的顶点扩充称为属性顶点和称为属性边的新边。属性顶点vati表示属性值对（at，ati），其中转换成不同的区间值。这些方法的缺点是，它们仅限于具有很少属性值的小网络。2.1.3基于质量函数优化的方法。 这一系列的方法扩展了众所周知的基于图的方法，考虑属性信息和拓扑结构。现有的方法主要是将Louvain算法[2]扩展为Newman [22]模块度和计算属性相似度的新度量的线性组合。Cruz al.[8]包括熵优化作为模块化优化和社区聚集之间的这样做是为了通过在模块化优化期间发现的集群之间移动节点来这些步骤被迭代，直到模块性不再被改进。在[9]中，作者提出了Lou-vain算法[2]，通过包括修改模块性TIDOM（AT）是属性AT的值。如果顶点v在属性at上具有值ati，则在顶点v和属性顶点vati之间添加属性边。有了这样的图增广-的属性相似性表示为顶点邻域由下式给出的属性的相似性Q+=。.α。[（Avu − λ）]+（1 −α）。S（u，v）增广图：共享相同属性值的两个顶点由公共属性顶点连接。因为每个顶点v i 具有T个属性值，则总共有 T条属性边添加到原始图中。在增广图中，两个顶点2米2米Ci∈Pv，u∈Ci如果它们通过许多其他原始顶点连接，或者如果它们作为邻居共享许多公共属性顶点，则它们是接近的一旦创建了增强图，就可以应用估计成对顶点接近度的距离度量或社区检测算法来找出簇的集合。接下来，在算法中2、形式化地给出了基于增广图的属性网络算法的原理。算法2基于增强图的方法要求：（，E，，F）：属性图。聚类：聚类算法确保：V的分区。1：V′=V∪Va; Va={（at，ati）}其中t∈ {1.. T}且i∈dom（at）2：E′=E∪Ea，其中EaV×Va第三章： G′=（V′，E′）4：P=簇（G’）5：返回P作者在[34]、[5]中提出了利用邻域随机游走距离计算扩充图上顶点之间统一距离的SA-Cluster算法。两个顶点之间的随机游走距离基于由结构边和属性边组成的路径。通过这种方式，它结合了结构其中S（v，u）是基于v和u的属性类型的相似性函数，并且它可以根据属性如何被表示而被适配。α [0，1]是表示结构和属性信息的贡献程度的加权因子。Louvain的另一个扩展由[7]提出，称为ILouvain算法，其使用基于惯性的模块化结合纽曼模块性优化方法假设图的最佳划分是最大化模块性的划分，但[12]，[16]已经表明，如果模块性不是某些图的相关度量，则不能满足此假设。2.2基于属性的方法与基于拓扑的方法不同，基于属性的方法旨在使用拓扑信息找到网络中的稠密连通子图，基于属性的方法计算所有节点对之间的距离矩阵或不相似矩阵。接下来，我们提出了不同的方式来考虑的拓扑结构信息。2.2.1统一的基于距离的方法。 这种方法将网络的拓扑信息转化为顶点间的相似度或距离函数。通常，该距离被定义为结构距离函数和节点属性距离之间的线性组合。一旦定义了该函数例如，我们有：连续属性通常，对于连续属性，值为跟踪：挖掘属性网络WWW 2018，2018年4月23日至27日，法国里昂1302•∈一dis（u，v）=αdisT（du，dv）+（1−α）disS（u，v）（2）其中：在一些实施例中，用户可以选择相同的聚类，以便建立产生组合聚类的成对相似性度量作者在[10]中将Louvain [2]，Licod [32]的拓扑聚类算法的结果与dis T（du，dV）：表示顶点u和v之间的拓扑距离。不同的拓扑距离可以作为最短路径、邻域随机游走距离等。disS（du，dv）：是顶点u和u之间的属性距离。v.α[0，1]：是被引入以控制两个相似性方面的影响的参数。结构和上下文相似性的重要性是变化的，并且取决于应用领域。因此，为该参数选择适当的值是至关重要的。例如，社交网络通常表现出密集区域，并遵循幂律度分布。较高的α值似乎对这些网络有效，因为密集区域中的节点预计具有相似的属性。然而，无标度的自由网络，例如道路网络，需要以平衡的比率来处理。例如，[6]，将统一距离定义为两个距离的线性组合，每个距离对应于一种数据类型：文本信息上的余弦距离和网络结构上的测地距离。然后，层次凝聚聚类应用与统一的距离矩阵。SAC算法中的[9]提出了另一个类似的统一距离函数，该函数将用于构建k-最近邻图。社区将被发现使用鲁汶算法。作者在[11]中提出了另一种考虑网络拓扑结构的方法，即ANCA。首先，它们选择一组称为种子的合格节点，这些节点是网络中的地标，将用于表征节点集图中每个顶点的位置将由其与种子节点的关系来表征一旦选择了种子，拓扑特征即距离将用于表征种子与网络的所有节点之间的关系。然后，使用加权因子，融合拓扑结构特征和属性信息。将拓扑信息封装在属性中，丰富了维空间。为此，作者使用谱聚类技术，以找到社区。2.3混合方法这类方法分别考虑属性信息和拓扑结构。接下来，我们简要解释处理这种方法的以下方法2.3.1基于集成/选择的方法。这些方法包括使用不同的聚类方法组合聚类的结果。可以使用集成方法来组合找到的分区。例如，超图分割算法（HGPA）[28]，其中集群集成问题通过切割最小数量而被视为超图的分割问题 的超边，近似的最大互信息的目标与最小切割目标的约束。或者…基于群集属性，即K-means方法另一方面，[18]提出了合并4个模型的方案。它们结合了拓扑聚类算法、属性聚类算法、基于属性的方法和GAMER算法[14]。2.3.2基于概率模型的方法。基于模型的方法制定了一个联合建模的边连接和顶点属性之间的相互作用，并利用这个模型来计算聚类。Xu等人[30]开发了一个表示为BAGC的属性图的贝叶斯概率模型，然后将聚类问题公式化为标准概率推理问题，以找到给出最高概率的聚类。概率模型本质上定义了所有可能的聚类和所有可能的属性图的空间上的联合概率分布。对于待聚类的每个顶点的簇标签被表示为隐藏变量。该模型通过断言顶点的属性值和边连接应取决于其簇标签来强制执行簇内相似性。特别是，同一聚类内顶点的属性值和边连接BAGC开始于将顶点随机分配到簇中。然后，迭代地重新计算所有分布的参数。更正式地说，给定一个属性化的图G由其邻接矩阵Madj、其属性矩阵M和向量Z定义，包含节点到簇的分配该模型产生联合概率p（Madj，MA，Z），并找到一个分区Z*使得：Z*=arдmaxZp（Madj，MA，Z）（3）BAGC模型最近已扩展到处理加权属性图[31]。CESNA[33]在属性图上定义了一个模型CESNA模型的顶点属性和连接在同一集群与伯努利分布。CESNA与BAGC的不同之处在于识别重叠的社区。3实验在本节中，我们进行了实验，以比较一组属性网络社区检测算法。这些最先进的算法是SA-Cluster[34] ， SAC[9] ，IGC-CSM[19]，NAS[27]，ILouvain [7]，ANCA[11]。我们还使用R中名为igraph的开源图形库从头开始开发了前面引用的算法，用于实验分析。其他的比较分析已经进行，我们已经消耗了聚类的结果，这是Ilouvain算法[7]1的情况。源代码的做法，评价措施相似性划分算法（CSPA）[28]，其中二进制相似性larity矩阵用于表示1http://bit.ly/ILouvain··跟踪：挖掘属性网络WWW 2018，2018年4月23日至27日，法国里昂1303K.不i=1δ（{ C}i=1）=E中文（简体）pkslogpksu∈C¯i，v∈Vs=1并且用于本文中的实验的数据集可作为R库下载23.1算法质量评价指标在这项研究中，我们使用两组指标来评估每个算法的性能。第一组包括NMI（归一化互信息）和ARI（调整后的兰德指数）。这些通常用于评估聚类结果时，地面实况分解成集群是已知的。值越高，表示算法性能越好。另一组由模块性、密度、电导和熵组成。模块度、密度和电导率用于衡量网络中社区的质量，值越大表示分区质量越好。用熵来度量社区中属性的一致性程度，并1.000.750.500.250.00100个基准数据集上评价方法的调整rand指数算法：kmeans鲁汶WalktrapANCA伊卢万Var2较低的熵值指示较大的一致性。当算法在没有地面实况的网络上运行时，通常使用这些met-rics。正式定义如下：密度：通过使用密度函数来分析顶点之间的强连接，该密度函数表示聚类中出现的边的数量与整个图中的边的总数之间的比率。所有聚类的比率被累积以评估总体影响。密度值位于[0， 1]的区间内。图1：100个合成数据的聚类ARI质量比较在100个基准数据集上评估方法的NMI1.000.75算法：鲁汶K1 .我i=10.50WalktrapANCA伊卢万熵：衡量聚类结果质量的一个关键方面是根据顶点的属性来确定顶点之间的相关性。对于每个属性的熵，在方程。3.1中所描述的方法，针对具有相关联属性的每个聚类来计算当同一聚类内的所有折点都具有相似的属性或关联的上下文时0.250.00Var2有了它们，则总熵获得最小值。K图2：100个合成数据熵（a）=Cii=1Ventropy（at，Ck）（4）.¯Auv（C）=u∈Ci，v∈Ci阿格德岛m（at）ttimin（ .一个uv，.Auv）其中pt值为是簇Ck中的顶点的分数，其中s∈dom（at）3.2合成的实验结果网络模块性：模块性是下降的边的数量在簇内减去具有随机放置的边的等效网络中的预期数量。模块性可以是正的或负的，正值指示可能存在的社区结构。[17 ][18][19]提供了一种生成具有社团结构和数值节点属性的网络的生成器。我们使用这个生成器来生成100个不同形状的属性网络，其中地面真实分解为社区是已知的。拟议的发电机提供属性网络与k1。 . ......你好。dudvΣΣ仅数值节点属性值。Q（{ C}i=1）=2mi=1u，v∈CiAuv−λ2m（五）用ILouvain算法和ANCA算法算法，Louvain算法，k-均值算法，因为它们电导率：分区的电导测量集群的紧密程度。处理具有数值节点属性的网络。图1和图2分别呈现了调整后的rand指数（ARI）和Φ（{C}k ）=的2lipn.univ-paris13.fr/f~ alih/packages/ANCL/（Ci）k归一化互信息（NMI），在100个属性网络上产生结果证实了使用这两种信息的兴趣，因为ILouvain和ANCA优于其他方法。AriNMI··S·K·entropy（ at，Ck）=−u∈Ci，v∈V跟踪：挖掘属性网络WWW 2018，2018年4月23日至27日，法国里昂13040.620.49零 点五一0.460.370.250.170.20.160.130.060.080.040.010.20.80.750.640.570.510.520.470.380.370.280.250.210.470.550.9≥≥DBLP10k上的模块化质量比较DBLP10k上的内部密度质量比较一点一点0.750.500.25算法ANCAkmeansLouvainSACSACluster0.750.500.25算法ANCAkmeansLouvainSACSACluster0.0010100二百五十八群集号8320.0010100二百五十八群集号8321.00DBLP10k的密度质量比较1.00DBLP10k的电导质量比较0.750.500.25算法ANCAkmeansLouvainSACSACluster0.750.500.25算法ANCAkmeansLouvainSACSACluster0.00 0.0010 100 200 58 832群集号10 100 200 58 832群集号图3：DBLP10K数据只考虑一种类型的信息。与ILouvain算法相比，ANCA算法具有更好的效果。3.3真实网络上的实验结果除了使用合成网络的实验之外，我们还在两个真实网络上测试了算法。节点与分类属性相关联。关于这些数据集的详细信息如下所述。DBLP10K：是从DBLP中提取的合著者网络参考书目。每个顶点表示一个学者，每个边表示两个学者之间的合著者关系。该数据集包含10000名在主要会议上发表过论文的学者每个学者都与两个属性相关联，多产和初级话题属性“多产”具有三个值：发表论文20篇的学者为“高度多产”，发表论文10篇和20篇的学者为“多产”<，发表论文20篇的学者为“低多产”<10篇出版物属性“primary topic”的域为100个研究课题。然后，每个学者被分配一个主要的主题，从100个主题。这是由[19]给出的数据集。电子邮件：由于电子邮件隐私问题，没有公共语料库除了一个巨大的匿名安然电子邮件语料库[25]。它包含了大量的电子邮件，涵盖了41个月的时间跨度，也独特地描绘了能源巨头安然的起伏。它提供了一个机会图4：DBLP10K数据的电导率和内部密度质量基于相关邮箱用户在电子邮件网络中的唯一通信和关系来确定相关邮箱用户我们已经考虑了安然电子邮件数据集5，其中包含161个用户的所有电子邮件，单独管理，推断社区结构的部分信息，可在个性化的电子邮件。两个用户，莎莉贝克和路易丝厨房，电子邮件网络是利用从这个数据集的所有实验在本文中推断的社区结构。与安然公司以外的个人的电子邮件交互被明确忽略，以反映事实关联。对于真实世界的数据，通常无法获得地面实况。然而，我们可以用拓扑度量作为模块度，电导和属性度量作为熵来比较集群的质量。因此，我们分析了ANCA，Kmeans，Louvain，SAC，SACluster确定的聚类结果的下一个不同的属性。SA-Cluster，k-means，ANCA需要聚类的数量作为输入。对于DBLP 10 k数据集，我们设置聚类数k=10， 100， 200;对于电子邮件数据集，我们设置聚类数k=10， 20， 30，我们也比较拓扑的方法，只有方法作为鲁汶。它认为-仅描述网络的拓扑结构。我们还向k添加了由算法发现的社区数量，这些算法在DBLP10k和电子邮件上的实验结果如图3、4、5和6所示。0.750.640.510.520.470.380.370.340.280.250.210.040.470.550.90.990.760.52零点五四0.520.440.320.340.270.240.260.140.120.130.2密度模块化电导内部密度跟踪：挖掘属性网络WWW 2018，2018年4月23日至27日，法国里昂\1.000.750.500.250.001.000.750.500.250.00电子邮件的内部密度质量比较10 19 20 24 30 5069群集号电子邮件的电导质量比较10 19 20 24 30 5069群集号算法ANCAIGC−CSMkmeansLouvainSACSAClusterWalktrap算法ANCAIGC−CSMkmeansLouvainSACSAClusterWalktrap最好的方法应该同时保持原始图中顶点之间的稠密连通性密度、电导率和模块性测量顶点周围对于ANCA，这些拓扑质量度量是相关的，并且它们随着k的增加而减小。密度值表明，SA-聚类发现的簇比ANCA发现的簇密度大。然而，模块化和电导值的SA-集群给出了相反的观点。通过对聚类分布的分析，SA-Cluster算法发现了一个大的聚类，而其他聚类中的顶点很少从图中的数据中，我们得出结论，在大多数情况下，添加顶点属性可以提高社区检测以ANCA算法为例，大部分结果在拓扑结构上优于基本Louvain算法，在节点属性上优于k4结论在本文中，我们提供了一个概述的新兴主题的聚类属性图。只有少数的作品已经提出了在文献中，他们的目的是分区属性图到密集的集群与顶点具有相似的属性。现有的方法可以分为三个主要的方法的基础上的方式，拓扑和属性数据考虑了然后，我们在人工数据和真实数据上比较了一套属性网络中世界数据引用[1] 马丁·阿兹穆勒2015年。Subgroup and Community Analytics on属性图6：电子邮件数据的电导和内部密度质量电子邮件的模块化质量比较1.00图表..在SNAFCA@ ICFCA。[2] Vincent D Blondel，Jean-loup Guillaume，and Etienne Lefebvre.2008年在大型网络中快速统计力学杂志：理论与实验2008（2008），P10008. arXiv：arXiv：0803.0476v2[3] 布 丽 吉 特 · 博 登 2014 年 图 和 属 性 数 据 的 组 合 聚 类 。 ApprimusWissenschaftsver.[4] Cecile Bothorel ， Juan David Cruz ， Matteo Magnani ， and BarboraMicenková.2015 年 。 聚 类 属 性 图 ： 模 型 、 措 施 和 方 法 。 NetworkScienceJanuary （ 2015 ） ， 1-37. https://doi.org/10.1017/nws.2015.9arXiv ：1501.01670.750.500.250.001.000.750.500.2510 19 20 24 30 5069群集号电子邮件的密度质量比较算法ANCAIGC−CSMkmeansLouvainSACSAClusterWalktrap算法ANCAIGC−CSMkmeansLouvainSACSAClusterWalktrap[5] 洪成，杨舟，徐宇。2011.聚类大型属性图：结构相似性和属性相似性之间的平衡。ACM翻译知识发现。 数据5，2（2011），12：1- 12：33。https://doi.org/10.1145/1921632。 1921638[6] David Combe，Christine Largeron，El H Od Egyed-Zsigmond，and MathiasGéry.2012. 科 学 网 络 聚 类 中 关 系 与 文 本 的 结 合 。 2012IEEE/ACMInternational Conference on Advances in 社 交 网 络 Analysis and Mining（2012），1280-1285. https://doi.org/10.1109/ASONAM.2012.215[7] David Combe ， Christine Largeron ， Mathias Géry ， and Elöd Egyed-Zsigmond.2015年。I-Louvain ： 一 种 属 性 图 聚 类 方 法 。 在 智 能 数 据 分 析 的 进 展 XIV 。Springer，181[8] Juan David Cruz、Cécile Bothorel和François Poulet。2011.增强社交网络中基于熵的社区检测在计算方面的社交网络（cason），2011年国际会议。IEEE，163[9] TA Dang和E Viennet。2012.基于结构和属性相似性的社区发现。数字社会国际会议（ICDS）7-12[10] Haithum Elhadi和Gady Agam 2013. 结构和属性社区检测：综合、集合和选择方法的比较分析。Proceedings of the 7th Workshopon Social Network Mining and Analysis13 （ 2013 ） ， 10 ： 1- 10 ：7.https://doi.org/10.1145/2501025.25010340.0010 19 20 24 30 50 69群集号图5：电子邮件数据0.530.480.410.390.370.36 0.380.320.330.340. 三○四点三十0.30. 三0三点三二0.250.260. 205.240.250.250.020.790.590.560.520.480.460.460.40.270.220.290.260.20.150.160.120.120.070.050.070.080.010.420.270.270.270.230.240.220.220.150.160.130.103.130.130.110.120. 105.150.060.030.030.040.750.720.530.550.480.410.390.370.36 0.380.320.330.340.340.30.360. 三0三点三二0.260.205.240.25密度电导模块化内部密度1305跟踪：挖掘属性网络WWW 2018，2018年4月23日至27日，法国里昂[11] Issam Falih 、 Nistor Grozavu 、 Rushed Kanawati 和Younès Bennani 。 2017年。ANCA属性网络聚类算法。在复杂网络&及其应用VI - Proceedings of ComplexNetworks 2017（第六届复杂网络及其应用国际会议），复杂网络2017，法国里 昂 ， 2017 年 11 月 29 日 至 12 月 1 日 。 （ Studies in ComputationalIntelligence），Chantal Cherifi，Hocine Cherifi，Márton Karsai，and MircoMusolesi（Eds.），第689卷。Springer，241-252. https://doi.org/10.1007/978-3-319-72150-7_20[12] B. H. 很好YA. de Montjoye和A.克劳塞特2010年。实际环境中的模极大化性能Physical ReviewE，81（2010），046106.[13] Stephan Günnemann，Brigitte Boden，Ines Färber，and Thomas Seidl.2013年。有效图的子空间和子图簇的组合挖掘。太平洋亚洲知识发现和数据挖掘会议。Springer，261[14] Stephan Günnemann，Ines Farber，Brigitte Boden，and Thomas Seidl.2010年。子 空间聚类满足稠密子图挖掘：两种范式的综合。在数 据 挖 掘（ICDM），2010年IEEE第10届国际会议上。IEEE，845[15] David R.卡格一九九三年RNC中的全局最小切割，以及一个简单的Min-out算法。第四届ACM-SIAM离 散 算法 研 讨 会（ SODA'93 ） 工 业 与 应 用 数 学 学 会 ， 美 国 宾 夕 法 尼 亚 州 费 城 ， 21-30 。http://dl.acm.org/citation.cfm? 313559.313605[16] 安德里亚·兰奇基内蒂和桑托·福图纳托。2011年。社区检测中模块化最大化的限制CoRRabs/1107.1（2011）。[17] Christine Largeron、Pierre-Nicolas Mougel、Reihaneh Rabbany和Osmar R.Zaïane 2015 年 。 用 社 区 生 成 属 性 网 络 Plos One10 ， 4 （ 2015 ） ，e0122777.https://doi.org/10.1371/journal.pone.0122777[18] 纳西夫·穆斯林2016年。一种利用结构和属性数据的社交网络社区发现组合方法（2016年）。[19] Waqas Nawaz 、 Kifayat-Ullah Khan 、 Young-Koo Lee 和 Sungyoung Lee 。2015 年 。 基 于 协 同 相 似 性 度 量 的 图 内 聚 类 。 Distributed and ParallelDatabases（2015），583https://doi.org/10.1007/s10619-014-7170-x[20] 詹妮弗·内维尔，迈卡·阿德勒，大卫·詹森. 2003.使用属性和链接信息对关系数据进行聚类。在第18届人工智能国际联合会议的文本挖掘和链接分析研讨会上。9-15.[21] 马克EJ纽曼和亚伦Clauset。2016年。注释网络中的结构和推理NatureCommunications7（2016），11863.[22] M E J Newman。2003年。网络中的混合模式 物理审查。E，统计，非线性和软物质物理67，2 Pt 2（2003），026126。 https://doi.org/10。1103/PhysRevE.67.026126arXiv：cond-mat/0209450[23] M. E. J. Newman和M.格文2004.发现和评估网络中的 Phys. Rev. E 69，2（Feb. 2004），026113。 https://doi.org/10。1103/PhysRevE.69.026113[24] 作者声明：Daniel B. 作者声明：Dr. 2017. 地面实况关于元数据和社 区检 测在网 络 .科 学 -ence进 展3 、 5 （ 2017 ） 。arXiv：http://advances.sciencemag.org/content/3/5/e1602548.full.phttps://doi.org/10.1126/sciadv.1602548df[25] Jitesh Shetty和Jafar Adibi2004年安然电子邮件数据集数据库模式和简要统计报告。信息科学研究所技术报告，南加州大学4，1（2004），120[26] Jiibo Shi和Jitendra Malik。2000.归一化切割和图像分割。Pattern Analysisand Machine Intelligence，IEEE Transactions on22，8（2000），888[27] Karsten Steinhaeuser和Nitesh V Chawla。2008年大型现实社会网络中的社区检测在社会计算，行为建模和预测。Springer，168[28] A. Strehl和J.高希2003.集群集合：用于组合多个分区的知识重用框架。TheJournal of Machine Learning Research3（2003），583[29] Sebastian Thrun，Lawrence K Saul，and Bernhard Schölkopf（Eds.）. 2004.Advancesin Neural Information Processing Systems 16 [ 神 经 信 息 处 理 系 统 ，NIPS 2003，2003年12月8-13日，加拿大不列颠哥伦比亚省温哥华和惠斯