Multiscale Entropic Network Generation.

High-quality, large-scale network data is often not available for scientists, because of economic, legal, technological, or other obstacles. For example, the human contact networks along with infectious diseases spread are notoriously difficult to estimate, and thus our understanding of the dynamics and control of epidemics stems from models that make highly simplifying assumptions or simulate contact networks from incomplete or proxy data. In another domain, the development of cybersecurity systems requires testing across diverse threat scenarios and validation across diverse network structures that are not yet known. In both examples, the systems of interest cannot be represented by a single exemplar network, but must instead be modeled as collections of networks in which the variation among them may be just as important as their common features. Such cases point to the importance of data-driven methods for synthesizing networks that capture both the essential features of a system and realistic variability in order to use them in such tasks as simulations and verification.

Because existing methods only reproduce a limited set of specified network properties, we introduce a novel strategy for synthesizing artificial networks, namely, the multiscale entropic network generation (MUSKETEER). We create a hierarchy of coarse networks; but, in contrast to the multiscale methods for computational and optimization problems, we do not optimize anything but edit the network at all scales of coarseness. During the editing process we allow only local changes in the network. The editing problem (or generation) is formulated and solved at all scales where primitives at the coarse scale (such as coarse nodes and edges) represent aggregates of primitives and their fractions at previous finer scale. Analogous to multiscale methods for computational problems, by using appropriate coarsening we are able to detect and use the “geometry” behind the original network at multiple scales, which can be interpreted as an additional property that is not captured by other network generation methods. It is known that the topology of many complex networks is hierarchical and thus might be produced through iterations of generative laws at multiple scales. In general, such generative laws often can be different at different scales, as evidenced by the finding that complex networks are self-dissimilar across scales. For example, the number of triangles in the original network that one can be interested in can be completely different from the number of triangles at coarse scales. These differences can naturally be reflected in the proposed multiscale framework.

To evaluate the performance of MUSKETEER (http://www.cs.clemson.edu/ $\tilde{  }$ isafro/musketeer), we generated a large number of networks and compared them to the real-world networks (from epidemiology, social science, etc.) for a variety of local and global structural properties (such as clustering, modularity, and degree distribution). For most properties, the generated ensemble yields a median value close to the original value and range of values that is fairly symmetric about the median.