7,129
个编辑
更改
跳到导航
跳到搜索
第111行：
第111行： + 第116行：
第117行： − − 第126行：
第125行： − 第192行：
第190行： − 第217行：
第214行： + 第396行：
第394行： + 第401行：
第400行： − 第412行：
第410行： −
→社团检测算法
}}
}}
</ref>
</ref>
===层次聚类===
===层次聚类===
在网络中检测社团结构的另一种方法是'''层次聚类 Hierarchical clustering '''。 在这种算法中，定义了一种'''相似性度量 Similarity measure '''，去量化节点对之间的某些(通常是拓扑的)相似性。 常用的测量方法包括'''余弦距离健康指数 Cosine similarity '''、'''雅卡德指数 Jaccard index ''',以及'''汉明距离健康指数邻接矩阵 Hamming distance between rows of the adjacency matrix '''。 然后根据该算法将相似的节点分组到同一个社团中。
在网络中检测社团结构的另一种方法是'''层次聚类 Hierarchical clustering '''。 在这种算法中，定义了一种'''相似性度量 Similarity measure '''，去量化节点对之间的某些(通常是拓扑的)相似性。 常用的测量方法包括'''余弦距离健康指数 Cosine similarity '''、'''雅卡德指数 Jaccard index ''',以及'''汉明距离健康指数邻接矩阵 Hamming distance between rows of the adjacency matrix '''。 然后根据该算法将相似的节点分组到同一个社团中。
有几种常见的分组方案，其中最简单的两种是单链接聚类和'''完全链接聚类 Complete linkage clustering '''。前者在不同群组中的所有节点对的相似度小于给定的阈值的情况下，将两个群组视为独立的社团; 后者则是在每个群组中的所有节点对的相似度大于给定的阈值的前提之下进行分组。 一个有趣的方法是使用各种相似或不同的测度，通过'''凸和 convex sums '''来改进层次聚类的性能。<ref>{{Cite journal|title = Weighting dissimilarities to detect communities in networks|journal = Phil. Trans. R. Soc. A|date = 2015-12-13|issn = 1364-503X|pmid = 26527808|pages = 20150108|volume = 373|issue = 2056|doi = 10.1098/rsta.2015.0108|first = Alejandro J.|last = Alvarez|first2 = Carlos E.|last2 = Sanz-Rodríguez|first3 = Juan Luis|last3 = Cabrera|bibcode = 2015RSPTA.37350108A}}</ref>
有几种常见的分组方案，其中最简单的两种是单链接聚类和'''完全链接聚类 Complete linkage clustering '''。前者在不同群组中的所有节点对的相似度小于给定的阈值的情况下，将两个群组视为独立的社团; 后者则是在每个群组中的所有节点对的相似度大于给定的阈值的前提之下进行分组。 一个有趣的方法是使用各种相似或不同的测度，通过'''凸和 convex sums '''来改进层次聚类的性能。<ref>{{Cite journal|title = Weighting dissimilarities to detect communities in networks|journal = Phil. Trans. R. Soc. A|date = 2015-12-13|issn = 1364-503X|pmid = 26527808|pages = 20150108|volume = 373|issue = 2056|doi = 10.1098/rsta.2015.0108|first = Alejandro J.|last = Alvarez|first2 = Carlos E.|last2 = Sanz-Rodríguez|first3 = Juan Luis|last3 = Cabrera|bibcode = 2015RSPTA.37350108A}}</ref>
另一个常见的社团检测算法是 '''Girvan-Newman 算法 Girvan–Newman algorithm '''<ref name=ComSocBio/> ：首先识别社群之间连接的边，然后去除这些边，留下的就是社团。 该方法利用图论中的中心性度量来进行识别，当边位于多对节点之间时，给每条边赋予一个较大的数字。
另一个常见的社团检测算法是 '''Girvan-Newman 算法 Girvan–Newman algorithm '''<ref name=ComSocBio/> ：首先识别社群之间连接的边，然后去除这些边，留下的就是社团。 该方法利用图论中的中心性度量来进行识别，当边位于多对节点之间时，给每条边赋予一个较大的数字。
'''Girvan-Newman算法'''返回的结果具有较好的质量，且由于它与许多标准软件包兼容，因此得到广泛应用。但其运行缓慢，在''n''个顶点和''m''条边的网络上耗费时长为''O(m2n)''，导致其并不适用于超过几千个节点的网络。<ref name=fast>
'''Girvan-Newman算法'''返回的结果具有较好的质量，且由于它与许多标准软件包兼容，因此得到广泛应用。但其运行缓慢，在''n''个顶点和''m''条边的网络上耗费时长为''O(m2n)''，导致其并不适用于超过几千个节点的网络。<ref name=fast>
<ref name="RenEEL-Modularity">{{cite web|title=RenEEL-Modularity|url=https://github.com/kbassler/RenEEL-Modularity}}
<ref name="RenEEL-Modularity">{{cite web|title=RenEEL-Modularity|url=https://github.com/kbassler/RenEEL-Modularity}}
</ref>
</ref>
模块度优化的有效性是值得怀疑的，因为已经证明模块度优化受分辨率的大小限制，这导致我们往往不能检测到比某个规模更小的集群；<ref>
模块度优化的有效性是值得怀疑的，因为已经证明模块度优化受分辨率的大小限制，这导致我们往往不能检测到比某个规模更小的集群；<ref>
|pmid=20481785 |arxiv=0910.0165|bibcode=2010PhRvE..81d6106G}}
|pmid=20481785 |arxiv=0910.0165|bibcode=2010PhRvE..81d6106G}}
</ref>
</ref>
===基于推论统计学的社团检测算法===
===基于推论统计学的社团检测算法===
}}
}}
</ref>
</ref>
===基于团结构的社团检测算法===
===基于团结构的社团检测算法===
团就是一个无向图的完全子图，团中的每个节点都与团中的其他节点相连。 由于节点之间的联系不可能比这更紧密，所以在网络中产生了很多基于团结构的社团检测算法，由此还可以分析具有重叠性的社团结构。在这些算法中，一个节点可以同时属于多个社团，从而形成一个“重叠的社团结构”。
团就是一个无向图的完全子图，团中的每个节点都与团中的其他节点相连。 由于节点之间的联系不可能比这更紧密，所以在网络中产生了很多基于团结构的社团检测算法，由此还可以分析具有重叠性的社团结构。在这些算法中，一个节点可以同时属于多个社团，从而形成一个“重叠的社团结构”。
如果一个团不被其他任一团所包含，即它不是其他任一团的真子集，则称该团为图的'''极大团 maximal clique''' 。基于团的社团检测算法其中的一种方法就是找到“极大团” 。(其简单思想是：生成原始图的所有子图(可能有2n-1个子图，n表示节点个数）→判断这些子图是不是团→删除非极大团的其他团）其中， '''Bron-Kerbosch 算法 The Bron–Kerbosch algorithm ''' 是找到极大团的经典算法之一。 最简单的方法是只考虑大于最小尺寸(节点数)的极大团。 这些团体的联合被定义为一个子图，其组件(断开的部分)被定义为社团。<ref name="Everett1998">
如果一个团不被其他任一团所包含，即它不是其他任一团的真子集，则称该团为图的'''极大团 maximal clique''' 。基于团的社团检测算法其中的一种方法就是找到“极大团” 。(其简单思想是：生成原始图的所有子图(可能有2n-1个子图，n表示节点个数）→判断这些子图是不是团→删除非极大团的其他团）其中， '''Bron-Kerbosch 算法 The Bron–Kerbosch algorithm ''' 是找到极大团的经典算法之一。 最简单的方法是只考虑大于最小尺寸(节点数)的极大团。 这些团体的联合被定义为一个子图，其组件(断开的部分)被定义为社团。<ref name="Everett1998">
}}
}}
</ref> 这些算法通常在诸如 UCInet 这样的'''社交网络分析软件 social network analysis software '''中实现。
</ref> 这些算法通常在诸如 UCInet 这样的'''社交网络分析软件 social network analysis software '''中实现。
另一种方法是使用固定大小的团体，设大小为<math>k</math>。 这些图的重叠可以用来定义一类 <math>k</math>- 正则超图或一种团图（线图的一种推广，此时<math>k=2</math>）。<ref name="Evans2010">{{cite journal
另一种方法是使用固定大小的团体，设大小为<math>k</math>。 这些图的重叠可以用来定义一类 <math>k</math>- 正则超图或一种团图（线图的一种推广，此时<math>k=2</math>）。<ref name="Evans2010">{{cite journal