liu09114的个人博客分享 http://blog.sciencenet.cn/u/liu09114

博文

基于改进的最大流方法的网络社团发现

已有 2796 次阅读 2013-9-27 17:47 |系统分类:论文交流| 网络

任何一个普通网络,我们都可以把它改造成二部网络。如下图

原来网络 $G$ 的节点分别位于二部网络 ${G}'$ 的两部分节点中,原网络 $G$ 的每条边也存在于 ${G}'$ 中,如图所示。

这样产生的新网络 ${G}'$ 拥有原网络 $G$ 二倍的点数与边数,连接性质不变。

回想最大流问题,在二部图的一端设置一个源点,另一端设置几个汇点,每个节点 $i$ 有 $k_{i}$ 的流值,向二部图的另一部分流去,最终流入汇点中,从源节点集合 $S$ 发出的流量减去流入点的集合 ${S}'$ , $S={S}'$ ,则流量损失少的话,这个点集合就可以看成是一个社团。

文章:Detecting Community by Revised Max-flow Method in Networks20130819.pdf

这个网络转化的方法或许可以用在更多方面。





https://blog.sciencenet.cn/blog-246621-728343.html

上一篇:越来越轻冷了
收藏 IP: 58.194.178.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-4-28 06:41

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部