社团检测

社团检测通常是指将网络中联系紧密的部分找出来,这些部分就称之为社团,那么也可以认为社团内部联系稠密,而社团之间联系稀疏 [1]。
社团检测侧重于找到网络中联系紧密的部分,而经常忽略节点的属性(attributes)[2]。

聚类,顾名思义是将属于同一类的目标聚在一起,通常在聚类之前我们是不知道目标有哪些类型,这也是一种典型的无监督学习方法。那么现在来想想我们熟知的聚类方法:k-means,层次聚类等。其中,最核心的一个部分是计算两个目标之间的距离(或者称为相似度),距离近则它俩是一类,距离远,那就自成一派,或者去找其它距离近的。当然,距离近只是其中一种方法,还有距离远或者怎么样,就看自己的判断。判断标准不是讨论的重点,重点是如何计算距离。欧式距离,曼哈顿距离,余弦相似度等,都是直接用目标特征构成的向量来计算的,没有考虑目标的边,度。所以,聚类侧重于找到一堆属性相似的目标,从而忽略了目标与目标之间的联系。

modularity

图的相关概念

  1. 入度
  2. 出度
  3. 图的密度 degree
    通过 nx.degree(G) 计算图的密度,其值为边数m除以图中可能边数(即n(n-1)/2
  4. 节点度中心系数
    通过 nx.degree_centrality(G) 计算节点度中心系数.
    通过节点的度表示节点在图中的重要性,默认情况下会进行归一化,其值表达为 节点度d(u)除以n-1(其中n-1就是归一化使用的常量). 由于可能存在循环, 所以该值可能大于1.
  5. 节点距离中心系数
    通过nx.closeness_centrality(G)计算节点距离中心系数.
    通过距离来表示节点在图中的重要性, 一般是指节点到其他节点的平均路径的倒数,这里还乘以了n-1.
    该值越大表示节点到其他节点的距离越近,即中心性越高。
  6. 节点介数中心系数
    通过nx.betweenness_centrality(G)计算节点介数中心系数.
    在无向图中, 该值表示为节点作占最短路径的个数除以((n-1)(n-2)/2);
    在有向图中,该值表达为节点作占最短路径个数除以((n-1)(n-2)).
  7. nx.transitivity(G)//图或网络的传递性。即图或网络中,认识同一个节点的两个节点也可能认识双方,计算公式为3*图中三角形的个数/三元组个数(该三元组个数是有公共顶点的边对数,这样就好数了)。
  8. nx.clustering(G)//图或网络中节点的聚类系数。计算公式为:节点u的两个邻居节点间的边数除以((d(u)(d(u)-1)/2)。

[1]Newman M E, Girvan M. Finding and evaluating community structure in networks.[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 69(2):026113.

点击以访问 0308217.pdf

[2]Yang J, Mcauley J, Leskovec J. Community Detection in Networks with Node Attributes[J]. 2014:1151-1156.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据