机器学习——社区发现算法

机器学习——社区发现算法

    • 一、什么是社区?
    • 二、社区发现算法的应用场景
    • 三、社区发现算法

一、什么是社区?

答:同一社区内的节点与节点之间的连接很紧密,而社区与社区之间的连接比较稀疏。

设图 G = G ( V , E ) G= G(V,E) G=G(V,E),所谓社区发现是指在图G中确定nc( ≥ 1 \geq 1 1)个社区:
C = { C 1 , C 2 , . . . , C n c } (1) C= \{C_{1},C_{2},...,C_{nc}\}\tag{1} C={C1,C2,...,Cnc}(1)
使得各社区的顶点集合构成V的一个覆盖。

若任意两个社区的顶点集合的交集均为空,则称C为非重叠社区,否则称为重叠社区。
机器学习——社区发现算法_第1张图片
如下图所示,不同颜色的属于不同的社区,中间的部分属于多个社区
机器学习——社区发现算法_第2张图片

二、社区发现算法的应用场景

  • 在社交网络中社区圈子的识别(Community Detection)
  • 基于好友关系为用户推荐商品或内容
  • 社交网络中人物影响力的计算
  • 信息在社交网络上的传播模型
  • 虚假信息和机器人账号的识别、
  • 就与社交网络信息对股市、大选的预测
  • 互联网金融行业中的反欺诈预测

三、社区发现算法

在说社区发现算法之前,有必要说图的结构。
给出一些定义:

一个具体的网络可以抽象为一个由节点集合V(Vertex或node)和边(edge)集合E组成的图G=(V,E),节点数记为n=|V|,边数记为m=|E|。

衡量指标:

  • 度(degree):入度(比如微博上多少人关注我)和出度(比如微博上我关注多少人)
  • 密度(density)
  • 团(clique)
  • 度中心性(deg0.+58ree centrality)
  • 紧密中心性(closeness centrality)
  • 介数中心性(betweenness centrality)
  • 聚集系数(clustering coefficient)

未完待续……

你可能感兴趣的