||
任何一个普通网络,我们都可以把它改造成二部网络。如下图
原来网络 $G$ 的节点分别位于二部网络 ${G}'$ 的两部分节点中,原网络 $G$ 的每条边也存在于 ${G}'$ 中,如图所示。
这样产生的新网络 ${G}'$ 拥有原网络 $G$ 二倍的点数与边数,连接性质不变。
回想最大流问题,在二部图的一端设置一个源点,另一端设置几个汇点,每个节点 $i$ 有 $k_{i}$ 的流值,向二部图的另一部分流去,最终流入汇点中,从源节点集合 $S$ 发出的流量减去流入点的集合 ${S}'$ , $S={S}'$ ,则流量损失少的话,这个点集合就可以看成是一个社团。
文章:Detecting Community by Revised Max-flow Method in Networks20130819.pdf
这个网络转化的方法或许可以用在更多方面。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-5-24 00:47
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社