The use of sparsest cuts to reveal the hierarchical community structure of social networks |
| |
Authors: | Charles F. Mann David W. Matula Eli V. Olinick |
| |
Affiliation: | 1. Department of Computer Science and Engineering, Southern Methodist University, United States;2. Department of Engineering Management, Information and Systems, Southern Methodist University, United States |
| |
Abstract: | 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. |
| |
Keywords: | Network structure Community structure Social networks Maximum concurrent flow Sparsest cut Multipartite cut Divisive algorithm Graph theory |
本文献已被 ScienceDirect 等数据库收录! |
|