2006 StructuralInferenceOfHierarchiesInNetworks
- (Clauset et al., 2006) ⇒ Aaron Clauset, Cristopher Moore, Mark Newman. (2006). “Structural Inference of Hierarchies in Networks.” In: Proceedings of 23rd International Conference on Machine Learning (ICML 2006).
Subject Headings: Network Analysis
Notes
Cited By
Quotes
Abstract
One property of networks that has received comparatively little attention is hierarchy, i.e., the property of having vertices that cluster together in groups, which then join to form groups of groups, and so forth, upthrough all levels of organization in the network. Here, we give a precise definition of hierarchical structure, give a generic model for generating arbitrary hierarchical structure in a random graph, and describe a statistically principled way to learn the set of hierarchical features that most plausibly explain a particular real-world network. By applying this approach to two example networks, we demonstrate its advantages for the interpretation of network data, the annotation of graphs with edge, vertex and community properties, and the generation of generic null models for further hypothesis testing.
References
- [1] Albert, R., & Barab´asi, A.-L. (2002). Statistical mechanics of complex networks. Rev. Mod. Phys., 74, 47–97.
- [2] Bansal, N., Blum, A., & Chawla, S. (2004). Correlation clustering. ACM Machine Learning, 56, 89–113.
- [3] Barab´asi, A.-L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286, 509–512.
- [4] Bryant, D. (2003). A classification of consensus methods for phylogenies. In M. Janowitz, F.-J. Lapointe, F. R. McMorris, Boris Mirkin, and F. Roberts (Eds.), Bioconsensus, 163–184. DIMACS.
- [5] Casella, G., & Berger, R. L. (1990). Statistical inference. Belmont: Duxbury Press.
- [6] Clauset, A., Newman, M. E. J., & Moore, C. (2004). Finding community structure in very large networks. Phys. Rev. E, 70, 066111.
- [7] Girvan, M., & Newman, M. E. J. (2002). Community structure in social and biological networks. Proceedings of Natl. Acad. Sci. USA, 99, 7821–7826.
- [8] Trevor Hastie, Tibshirani, R., & Jerome H. Friedman (2001). The elements of statistical learning. New York: Springer.
- [9] Hastings, M. B. (2006). Community detection as an inference problem. Preprint cond-mat/0604429.
- [10] Jon Kleinberg (2000). The small-world phenomenon: an algorithmic perspective. 32nd ACM Symposium on Theory of Computing.
- [11] Newman, M. E. J. (2002). Assortative mixing in networks. Phys. Rev. Lett., 89, 208701.
- [12] Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Review, 45, 167–256.
- [13] Newman, M. E. J. (2004). Detecting community structure in networks. Eur. Phys. J. B, 38, 321–320.
- [14] Newman, M. E. J., & Barkema, G. T. (1999). Monte carlo methods in statistical physics. Oxford: Clarendon Press.
- [15] Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., & Parisi, D. (2004). Defining and identifying communities in networks. Proceedings of Natl. Acad. Sci. USA, 101, 2658–2663.
- [16] Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. N., & Barab´asi, A.-L. (2002). Hierarchical organization of modularity in metabolic networks. Science, 30, 1551–1555.
- [17] Sales-Pardo, M., Guimer´a, R., Moreira, A. A., & Amaral, L. A. N. (2006). Extracting and representing the hierarchical organization of complex systems. Unpublished manuscript.
- [18] S¨oderberg, B. (2002). General formalism for inhomogeneous random graphs. Phys. Rev. E, 66, 066121.
- [19] Stanley Wasserman, & Faust, K. (1994). Social network analysis. Cambridge: Cambridge University Press.
- [20] Stanley Wasserman, and G. L. Robins. (2005). “An Introduction to Random Graphs, dependence graphs, and p*.” In: P. Carrington, J. Scott, and Stanley Wasserman (Eds.), "Models and Methods in Social Network Analysis.” Cambridge University Press.
- [21] Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393, 440–442.
- [22] Zachary, W. W. (1977). An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33, 452–473.
,