您当前的位置:悬赏问答

2017-11-12 08:46

作业一:什么是模块度函数? 10

什么是模块度函数Q?谁提出的?如何推导的?具有哪些不足?

提问者采纳

2017-11-12 08:46

该函数源于“随机网络不会具有明显的社团结构”的思想,通过比较实际覆盖度(覆盖度是社团内部连接数占总连接数的比例)与随机连接情况下覆盖度的差异来评估社团结构。被广泛使用的评价函数就是模块度函数Q。模块度可用来比较不同社团结构划分的质量,如,发现最佳的层次结构分裂图、验证不同的社团结构发现算法以及作为优化过程的适应度函数。模块度也称模块化度量值,是目前常用的一种衡量网络社区结构强度的方法,最早由Mark NewMan 提出。

模块度的大小定义为社区内部的总边数和网络中总边数的比例减去一个期望值,该期望值是将网络设定为随机网络时同样的社区分配所形成的社区内部的总边数和网络中总边数的比例的大小,于是模块度Q为:

模块度值的大小主要取决于网络中结点的社区分配C,即网络的社区划分情况,可以用来定量的衡量网络社区划分质量,其值越接近1,表示网络划分出的社区结构的强度越强,也就是划分质量越好。因此可以通过最大化模块度Q来获得最优的网络社区划分。

研究发现模块度函数不能探测到一些较小的社团(相对整体网络而言),甚至当这些社团是派系(即完全图)时。那么,当最大模块度对应的社团结构划分中包含小于一定规模的社团时,就不能确定这些社团是单独的社团或更小社团的弱连接组合.

其他 1 条回答

2017-11-12 08:46

自然界和社会中的许多复杂关系可以被描述为网络或者图,系统的组成部分和他们之间的交互作用可视为网络中的节点和边。复杂系统通常由群组或者社团组织构成,不同的群组或者社团的功能角色不同。这种群组或者社团内节点连接较为紧密,群组间节点连接较为松散。

社团结构探测或者群组发现是复杂网络领域内的一个重要课题,也有很多的社团结构探测算法,根据多种的算法可以得到很多社团结构,为了辨别优劣——或衡量网络划分质量,则需要一个量化的标准来评估各种社团结构。

迄今为止,被最广泛使用的评价函数就是Newman在2004年Finding and evaluating community  structure in networks 一文中提出的模块度函数 Q 。它是指网络中链接社区结构内部定点的边所占的比例与另外一个随机网络中连接社区结构内部顶点的边所占比例的期望值相减所得到的差值。该随机网络的构造方法为:保持每个定点的社区属性不变,根据顶点的度随机链接顶点间的边。若社区结构划分的好,则社区内部连接的稠密程度应该高于随机连接网络的期望水平。

不足在于分辨率限制,当社团大小差异较大时不能探测到一些较小的社团




登录 后查看个人信息