机器学习和生物信息学实验室联盟

标题: 各类网络聚类中的评价指标：模块度 [打印本页]

作者: zsm 时间: 2016-11-22 10:08
标题: 各类网络聚类中的评价指标：模块度
一：论文介绍
   模块度的提出：
         论文题目：Finding and evaluating community structure in networks
         作者：MEJ Newman，M Girvan
         发表时间：2004
         发表处：Physical Review E Statistical Nonlinear & Soft Matter Physics
   模块密度：
         论文题目：Quantitative function for community detection.
         作者： Z Li，S Zhang，RS Wang，XS Zhang，L Chen
         发表时间：2008
         发表处：Physical Review E Statistical Nonlinear & Soft Matter Physics
   重叠社区的模块度：
         论文题目：Extending the definition of modularity to directed graphs with overlapping communities
         作者：V Nicosia，G Mangioni，V Carchiolo，M Malgeri
         发表时间：2009
         发表处：Journal of Statistical Mechanics Theory & Experiment
   二分模块度
         论文题目：Module identification in bipartite and directed networks.
            作者：R Guimerà，M Sales-Pardo，LA Amaral
            发表时间：2008
            发表处：Physical Review E Statistical Nonlinear & Soft Matter Physics

二：模块度的提出

      1：自下而上的聚类
         [attach]3090[/attach]

存在问题：
1：不能重复，找出的结构经常不一致，所以可扩展性不强。
2：只针对较强的点（类核心），忽略了比较边缘的点。

      2：自上而下的聚类
[attach]3091[/attach]

要解决的问题：
按照上述的方法把网络划分之后，如何找到最好的切割点。

[attach]3092[/attach]

这个设计的模块度存在的问题
1，优化模块度是 NP-hard 问题
         不能在多项式时间内解决。

2，模块度存在分辨率极限。
         不能够分辨出非常细小的网络。

3，只适用于一个节点属于一种类型的网络。
      重叠网络和二分网络的情况不适用。

三：模块密度

解决的问题：这个模块度的提出主要解决了Q模块度没有办法解决小结构社区的检测（分辨率问题）。
[attach]3093[/attach]

[attach]3094[/attach]

[attach]3095[/attach]

四：二分类模块度

1：什么是二分网络
[attach]3096[/attach]

2：一般处理二分网络的方式
[attach]3097[/attach]

3：二分网络聚类步骤
[attach]3098[/attach]

4：二分网络公式粗解
[attach]3099[/attach]

在二分网络中Q值的设计思想：X类型顶点集合中的顶点对共同连接的Y类型顶点个数占Y类型顶点
总个数比例的实际值和期望值的差异大小来量化。

5：有向图到二分网络的映射
[attach]3100[/attach]

五：重叠网络模块度

1：什么是重叠网络
[attach]3101[/attach]

2：如何找到属于多个网络的节点
[attach]3102[/attach]

3：计算过程
[attach]3103[/attach]

  4：推导公式
[attach]3104[/attach]5

[attach]3105[/attach]

  5：重叠网络聚类举例
[attach]3106[/attach]

六：对模块度理解和猜想

1：模块度可以理解成单目标优化问题中的损失函数，像分类数中的剪枝，SVM优化合页损失函数。

2:多目标优化就是把优化问题中的目标拆分成多个互相制约的目标转化为组合优化问题。

3：是否可以最很多优化算法的损失函数进行拆分，从而用多目标的方式来解决问题。

欢迎光临机器学习和生物信息学实验室联盟 (http://123.57.240.48/)