24小时热门版块排行榜    

查看: 1323  |  回复: 5

xiaoxiaosea

铜虫 (小有名气)

[求助] 求助,如何将一个图划分为几个大小相等的集群并集群间的互联度最小 已有1人参与

如题,请教各位高手,
    采用什么算法,能够运用图论原理,针对一个给定的通信互联图,选择最优的集群大小值,将其划分为多个大小相等的集群,并使得集群间的互联度最小。
如附件中的通信互联图

想要把他划分为多个相等大小的集群,
  1) 如何确定最优的集群大小值,如:是划分为3个集群大小为4的集群,还是4个集群大小为3的集群???
  2)如何实现集群划分,当规模较大时,什么算法划分较快且效果较好

     烦请告之相关算法,参考书及参考文献。
     欢迎关注,先行谢过

求助,如何将一个图划分为几个大小相等的集群并集群间的互联度最小
1.JPG



[ Last edited by xiaoxiaosea on 2013-10-10 at 15:04 ]
回复此楼
Icanfly.
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

xiaoxiaosea

铜虫 (小有名气)

高手快来呀。。。。
Icanfly.
2楼2013-10-10 15:07:44
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

feixiaolin

荣誉版主 (文坛精英)

优秀版主

1stop软件中附带的例子程序可以借鉴。
3楼2013-10-10 15:30:23
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

dameng

银虫 (小有名气)

问题定义不明确:
1.何为互联度?是指两个集群间的边的权重和吗?
2.何为集群大小相等?是指集群的顶点数相同吗?还是集群上所有顶点数值之和?我注意到你的顶点上也附有数值。
3.怎么算最优?我的理解是,对于确定的集群大小,存在相应的最小互联度划分;如何确定最优集群大小,使这个最小互联度最小,并给出划分方法。
4.如果不能整除怎么办?
呵呵,帮你明确下问题,其实我也不会。这个问题跟连通性和"割“有关,关键是要求集群大小相同。
研究方向:数据库。主要面向图数据管理、图数据挖掘、社会网络等。目前正在关注动态图算法。
4楼2013-10-10 15:39:57
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

dameng

银虫 (小有名气)

【答案】应助回帖

★ ★ ★ ★ ★ ★ ★ ★ ★ ★
感谢参与,应助指数 +1
xiaoxiaosea: 金币+10, ★有帮助, anyway,谢谢了,虽然还是米有答案出来 2013-10-22 14:12:20
内容已删除
研究方向:数据库。主要面向图数据管理、图数据挖掘、社会网络等。目前正在关注动态图算法。
5楼2013-10-11 22:37:07
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

amzheng

新虫 (初入文坛)

【答案】应助回帖

首选遗传算法啊,遗传算法的全局搜索能力非常适合于在问题规模较大时的图划分问题
6楼2014-11-26 12:55:01
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 xiaoxiaosea 的主题更新
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[硕博家园] 售SCI文章,我:8O.5.5.1O.54,科目全,可十急 +4 uKOSCocCb6Fm 2026-11-12 10/500 2026-11-16 22:49 by Equinoxhua
[论文投稿] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +4 XJXMuRjD7cK7 2026-11-13 4/200 2026-11-16 11:39 by K7HMGGdOpylw
[硕博家园] 售SCI一区文章,我:8.O.551.O.5.4,科目全,可伽急 +4 XJXMuRjD7cK7 2026-11-13 4/200 2026-11-16 11:28 by K7HMGGdOpylw
[考研] 售SCI一区T0P文章,我:8.O.55.1.O.5.4,科目全,可+急 +3 SX5mJmPWDfOO 2026-11-13 3/150 2026-11-15 07:56 by xSrQNSSjcgoX
[论文投稿] 售SCI一区文章,我:8.O.551.O.5.4,科目全,可伽急 +4 XJXMuRjD7cK7 2026-11-13 4/200 2026-11-15 07:01 by xSrQNSSjcgoX
[硕博家园] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +3 uKOSCocCb6Fm 2026-11-12 6/300 2026-11-15 02:59 by xSrQNSSjcgoX
[论文投稿] 售SCI一区T0P文章,我:8.O.55.1.O.5.4,科目全,可+急 +4 gRND4NVAZ8VG 2026-11-11 5/250 2026-11-13 11:15 by Equinoxhua
[教师之家] 售SCI一区文章,我:8O5.5.1.O5.4,科目全,可伽急 +6 czAiolzR0IJC 2026-11-10 6/300 2026-11-12 16:55 by zzy933268
[考博] 售SCI一区文章,我:8.O.55.1.O.54,科目齐全,可伽急 +4 TgvkbZZl9tqB 2026-11-11 6/300 2026-11-12 12:42 by ECLTXnJnRSXf
[硕博家园] 售SCI一区文章,我:8.O.551.O.5.4,科目全,可伽急 +3 TgvkbZZl9tqB 2026-11-11 4/200 2026-11-12 12:28 by ECLTXnJnRSXf
[公派出国] 售SCI一区文章,我:8.O.551.O.5.4,科目全,可伽急 +3 czAiolzR0IJC 2026-11-10 8/400 2026-11-12 11:11 by HajghKOMynmz
[考研] 售SCI一区T0P文章,我:8O.55.1.O.5.4,科目齐全,可+急 +7 czAiolzR0IJC 2026-11-10 9/450 2026-11-12 11:00 by HajghKOMynmz
[考研] 售SCI一区T0P文章,我:8O.55.1.O.54,科目全,可伽急 +4 G2rhSvqvhNzl 2026-11-10 7/350 2026-11-12 10:49 by HajghKOMynmz
[硕博家园] 售SCI-T0P文章,我:8O.5.5.1.O.54,科目齐全,可+急 +5 G2rhSvqvhNzl 2026-11-10 6/300 2026-11-12 10:30 by HajghKOMynmz
[教师之家] 售SCI一区文章,我:8.O.551.O.5.4,科目全,可伽急 +3 TgvkbZZl9tqB 2026-11-11 3/150 2026-11-12 08:26 by HajghKOMynmz
[基金申请] 售SCI一区文章,我:8.O.551.O.5.4,科目全,可伽急 +3 TgvkbZZl9tqB 2026-11-11 5/250 2026-11-12 08:15 by HajghKOMynmz
[考研] 售SCI一区文章,我:8.O.55.1.O.54,科目齐全,可伽急 +3 cdqGD6ftHmbl 2026-11-11 3/150 2026-11-12 07:53 by HajghKOMynmz
[公派出国] 售SCI一区T0P文章,我:8.O.55.1.O.5.4,科目全,可+急 +3 gRND4NVAZ8VG 2026-11-11 3/150 2026-11-12 07:42 by HajghKOMynmz
[公派出国] 售SCI一区T0P文章,我:8O.55.1.O.5.4,科目齐全,可+急 +3 czAiolzR0IJC 2026-11-10 5/250 2026-11-12 06:36 by 9fOTqj074tIg
[考研] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +3 Z7qfCsdIiD1T 2026-11-10 4/200 2026-11-12 02:23 by 9fOTqj074tIg
信息提示
请填处理意见