(295a) Coarse-Graining and Data Mining in Dynamical Network Systems

Coarse-graining and data mining in dynamical network systems

Understanding the long-term dynamics of complex networks is of importance to a large variety of fields from sociology to process engineering. These systems are often modeled as dynamic graphs. Here, we focus on the description of evolving networks, i.e. graphs whose connectivity changes over time. We apply the equations-free coarse-graining framework to investigate the overall network evolution of a network involving competition between fragmentation and coagulation [1]. Appropriate coarse variables are chosen based on analytical results previously derived for the system. Through coarse projective integration, this approach accelerates temporal simulations, while matrix-free Newton-Krylov GMRES is implemented to compute coarse-grained fixed points. Additionally, simulation data is compared with available analytical results.

Such theoretical results are unfortunately often unavailable, making the choice of coarse variables for the reduced models challenging. Thus, one would benefit more from a general data mining procedure to extract the intrinsic parameters (coarse variables) of the system making use of data (graphs) collected either empirically or from a model simulating the dynamical process.

To this end, we use a data mining approach called Diffusion Maps to analyze the graph data. Many standard data mining techniques (including Diffusion Maps) use a similarity measure defined on the data points. For our purposes, this translates to the requirement of defining a similarity measure in the space of graphs, i.e., defining a measure of closeness between two given graphs. We use two different approaches to define the similarity measure required by Diffusion Maps: (a) structural information using subgraph densities, and (b) a spectral method based on the idea of random walks. We present and compare results obtained using both approaches for our test examples.

[1] B. Ráth, B. Tóth. Erdos-Renyi random graphs + forest fires = self-organized criticality. Electronic Journal of Probability 14:1290-1327. (2009)