The use of sparsest cuts to reveal the hierarchical community structure of social networks
- 作者：Charles F. Mann ; David W. Matula ; Eli V. Olinick
- 关键词：Network structure ; Community structure ; Social networks ; Maximum concurrent flow ; Sparsest cut ; Multipartite cut ; Divisive algorithm ; Graph theory
- 刊名：Social Networks
- 出版年：2008
- 期刊代码：108_03788733
- 类别：soc
- 出版时间：July 2008
- 卷：30
- 期：3
- 页码：223-234
- 文件大小：1679 K
摘要
We show that good community structures can be obtained by partitioning a social network in a succession of divisive sparsest cuts. A network flow algorithm based on fundamental principles of graph theory is introduced to identify the sparsest cuts and an underlying hierarchical community structure of the network via maximum concurrent flow. Matula [Matula, David W., 1985. Concurrent flow and concurrent connectivity in graphs. In: Alavi, Y., et al. (Eds.), Graph Theory and its Applications to Algorithms and Computer Science. Wiley, New York, NY, pp. 543–559.] established the maximum concurrent flow problem (MCFP), and papers on divisive vs. agglomerative average-linkage hierarchical clustering [e.g., Matula, David W., 1983. Cluster validity by concurrent chaining. In: Felsenstein, J. (Ed.), Numerical Taxonomy: Proc. of the NATO Adv. Study Inst., vol. 1. Springer-Verlag, New York, pp. 156–166 (Proceedings of NATO ASI Series G); Matula, David W., 1986. Divisive vs. agglomerative average linkage hierarchical clustering. In: Gaul, W., and Schader, M. (Eds.), Classification as a Tool of Research. Elsevier, North-Holland, Amsterdam, pp. 289–301; Thompson, Byron J., 1985. A flow rerouting algorithm for the maximum concurrent flow problem with variable capacities and demands, and its application to cluster analysis. Master Thesis. School of Engineering and Applied Science, Southern Methodist University] provide the basis for partitioning a social network by way of sparsest cuts and/or maximum concurrent flow.