中文

English

介绍

关于社区发现和Girvan_Newman算法：

• 社区发现：Wiki
• 我的博客：GN算法， 针对加权图的GN算法
• Girvan–Newman算法：Wiki

实现：

Girvan_Newman算法

Zachary's karate club网络：

划分后的网络：

针对加权网络的Girvan_Newman算法

Les Miserables网络：

划分后的网络：

建议使用 Gephi 显示数据集文件，可以为网络提供一个非常直观的展示

数据集

Zachary's karate club: social network of friendships between 34 members of a karate club at a US university in the 1970s. W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33, 452-473 (1977).

Les Miserables: coappearance weighted network of characters in the novel Les Miserables. D. E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing, Addison-Wesley, Reading, MA (1993).

这两个数据集均来自Gephi 的 Sample Datasets

Gephi sample datasets 提供了有非常丰富的关于网络的数据集

参考文献

Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical review E, 2004, 69(2): 026113.

---

Introduction

Some about Community Structure和Girvan–Newman Algorithm：

• Community Structure：Wiki
• My post(Chinese) ：GN算法， 针对加权图的GN算法
• Girvan–Newman algorithm：Wiki

Implementation：

Girvan_Newman Algorithm

Original Network：

Divided network：

Girvan_Newman Algorithm for weighted graph

Original Network：

Divided network：

It is recommended to use Gephi to display dataset files. And it can provide a very intuitive presentation of networks

Datasets

The Girvan_Newman algorithm uses the Zachary's karate club dataset

Zachary's karate club: social network of friendships between 34 members of a karate club at a US university in the 1970s. W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33, 452-473 (1977).

The weighted Girvan_Newman algorithm uses the Les Miserables dataset

Les Miserables: coappearance weighted network of characters in the novel Les Miserables. D. E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing, Addison-Wesley, Reading, MA (1993).

Both datasets are from Gephi sample datasets

References

Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical review E, 2004, 69(2): 026113.