Supporting online material for Mapping change in large networks

Here we lay out the details of how we generate signifi-cance clusters and alluvial diagrams for mapping change in networks. Because this method assesses how much confidence we should have in the clustering of a network, we can detect, highlight, and simplify the significant structural changes that occur over time or between states in large networks, for example, citation networks, traf-fic networks, and monetary flow networks. The method consists of four steps, summarized here and described in detail below and in Fig. 1: 1. We partition or“cluster”the original real-world net-work, assigning each node to a single module, or community of closely associated nodes. 2. We generate a large number ( ∼ 1000) of boot-strap replicate networks, constructed by parametric bootstrap resampling of the original network. We cluster each of those networks. 3. To identify the significant assignments of nodes to modules in the original network, we search for the largest subset of nodes in a module that co-occur in at least 95 % of all bootstrap networks. To identify the significant modules, we search for all modules whose significant nodes are clustered with no other module’s significant nodes in at least 95 % of all bootstrap networks. 4. To map the changes in the network, we repeat the significance clustering for the different states of the network and generate an alluvial diagram, which highlights and simplifies changes in the significance clusterings. Significance clustering and alluvial diagrams This approach to mapping change in large networks works for any clustering algorithm. The choice of algo-rithm depends on the network type (undirected, directed