Evolving Networks: Structure and Dynamics

Network analysis, especially social network analytics, has become widespread due to the growing amount of linked data available. Many researchers have started to consider evolving networks, i.e. Time-Varying Graphs (TVGs), to begin to understand how these networks change over time.

In this dissertation, we expand on current practice in three directions: we define a new concept of “node-identity class” to describe different “lenses” over an evolving network, we develop sampling methods to produce representative static graphs over a network as it evolves, and we utilize social network metrics to produce distributions characterizing the dynamics of the network’s evolution. By combining these different techniques, we uncover a change effect in metric value due to network activity across sampling methods and window sizes, and produce a differential measure D(G) that helps signal possibly significant network evolution.

We evaluate these techniques on synthetically-generated datasets with prescribed dynamics to show their effectiveness at capturing and depicting those events. We then apply our techniques to analyze three real-world applications: the Nauvoo Marriage Project, consisting of an evolving Mormon marital network in mid-1800s Nauvoo, IL; the Social Networks and Archival Context Project’s historical social-document network; and an ArXiv co-authorship network. In each case, we were able to depict the network’s dynamics, highlight periods of network activity for further investigation, and guide domain-specific researchers to new insights. For the Nauvoo Marriage Project, through a comparison of the network across identity lenses, our metrics depicted an increased centrality under the patriarchal lens compared with that of the matriarchal lens. Indeed, the rapidity with which the patriarchal centrality “rebounds” suggests a desire of the Nauvoo community to form a strong patriarchal system.