Sampling Algorithms of Pure Network Topologies: Stability and Separability of Metric Embeddings

摘要

In a time of information glut, observations about complex systems and phenomena of interest are available in several application areas, such as bioinformatics, computational biology, and electronic text processing. As a consequence, scientists have started searching for patterns that involve interactions among the objects of analysis, to the effect that research on models and algorithms for network analysis has become a central theme for KDD. The intuition behind the plethora of approaches relies upon a few basic types of networks, which are identified by specific local and global topological properties, and which the authors term 'pure' topology types. In this paper, the authors do the following: (1) survey pure topology types along with existing sampling algorithms that generate them; (2) introduce novel algorithms that enhance the diversity of samples, and address the case of cellular topologies; (3) perform statistical studies of the stability of the properties of pure types to alternative generative algorithms; and (4) perform a joint study of the separability of pure types in terms of their embedding in a space of metrics for network analysis. The results show that the sampling algorithms entail low stability of topological properties entailed by alternative algorithms, and lead to weak separability topology types. The authors spell out the implications of these results for practitioners. They conclude that real world networks hardly present the variability profile of a single pure type, and suggest the assumption of 'mixtures of types' as a better starting point for developing models and algorithms for network analysis.