CGISID分享 http://blog.sciencenet.cn/u/wsh6759

博文

Betweenness Centrality 算法介绍与参考资料等

已有 11993 次阅读 2012-11-28 22:09 |个人分类:GIS修炼技术|系统分类:科研笔记| 社会网络, 网络中心性

                  Betweenness Centrality 算法介绍与参考资料等

 

   Betweenness Centrality是网络中心性重要的度量参数之一(下面简称BC)。在计算BC参数中,经典算法为参考1(1)中的Brander算法,而开源软件图 JUNG库计算BC的算法复杂度为O(n^2 + nm);而 计算无全图的算法复杂度为O(nm),计算有权图算法的复杂度为O(nm + n^2 log n);讲到这里不得不提伟大的BGL库,其计算BC的算法复杂度为:

 

 

1.计算BC经典算法

    (1)A Faster Algorithm for Betweenness Centrality, Ulrik Brandes, Journal of Mathematical Sociology, 2001, 25:2, pp. 163 - 177", "DOI: 10.1080/0022250X.2001.9990249"

    (2)On variants of shortest-path betweenness centrality and their generic computation, Ulrik Brandes, Social Networks, vol 30:2", pp. 136 - 145, 2008, issn 0378-8733, "DOI: 10.1016/j.socnet.2007.11.001".

2.简单计算BC例子 http://xrigher.info/cpp/an-example-of-boost-betweenness-centrality/

3. 非分布式计算BC方法 http://www.boost.org/doc/libs/1_50_0/libs/graph_parallel/doc/html/non_distributed_betweenness_centrality.html

4. 分布式计算BC方法 http://www.boost.org/doc/libs/1_50_0/libs/graph_parallel/doc/html/betweenness_centrality.html

5. JUNG计算BC http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/importance/BetweennessCentrality.html

6. graph-stream计算BC方法 http://graphstream-project.org/api/gs-algo/org/graphstream/algorithm/BetweennessCentrality.html

7. 使用邻接表计算BC  http://stackoverflow.com/questions/7706391/how-to-calculate-betweenness-using-boostlib-for-adjacency-list

8.使用BGL计算节点BC例子 http://xrigher.info/cpp/an-example-of-boost-betweenness-centrality/

9. BC简介 http://blog.csdn.net/jackiej/article/details/5195508

10.斯坦福大学网络分析库 http://snap.stanford.edu/index.html

11.boost dijkstra算法例子 http://blog.csdn.net/ccsdu2004/article/details/3868648

 

 



https://blog.sciencenet.cn/blog-216007-637220.html

上一篇:pugxml项目介绍
下一篇:空间分析理论方法经典论文

0

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

数据加载中...

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

GMT+8, 2022-6-30 13:16

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部