In a time of information glut, observations about complex systems and phenomena of interest are available in several applications areas, such as biology and text. As a consequence, scientists have started searching for patterns that involve interactions among the objects of analysis, to the e ect that research on models and algorithms for network analysis has become a central theme for KDD. The intuitions behind the plethora of approaches rely upon few basic types of networks, identified by specific local and global topological properties, which we term pure topology types. In this paper, (1) we survey pure topology types along with existing sampling algorithms that generate them, (2) we introduce novel algorithms that enhance the diversity of samples, and address the case of cellular topologies, (3) we perform statistical studies of the stability of the properties of pure types to alternative generative algorithms, and a joint study of the separability of pure types, in terms of their embedding in a space of metrics for network analysis, widely adopted in the social and physical sciences. We find that the sampling algorithms entail low stability of topological properties entailed by alternative algorithms, and lead to weakly separability topology types. We spell out the implications for the practitioners. We 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.

22 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu