The use of sparsest cuts to reveal the hierarchical community structure of social networks

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.