Workshop 3: Modeling and Analysis of Dynamic Social Networks

(November 7,2018 - November 9,2018 )

Organizers


Ian Hamilton
EEOB/Mathematics, The Ohio State University
Keith Warren
Social Work, The Ohio State University

This event will be hosted in the MBI Auditorium, Jennings Hall 355

In recent years, the focus of social network theory in behavioral ecology and the social sciences has shifted to understanding the dynamics of social networks. Data analytical methods such as relational state models and others have been used to address patterns of network change over time as agents gain or lose ties and how network structure coevolves with the attributes of agents in real-world networks. Network models are beginning to incorporate data at multiple scales and multiple types of interactions.  New technologies have facilitated collection of large quantities of data in many systems allowing increasingly sophisticated analyses of changes in social structure over time.  

Mathematical and empirical challenges arise because social networks are complex systems that emerge from, as well as influence, the interacting decisions of multiple, autonomous, objective-maximizing or goal-oriented agents.  Agents often have multiple types of relations, resulting in multilayer (multiplex) networks.  Current techniques for data analysis of dynamic networks are best suited to address enduring relationships, rather than momentary interactions, but many social interactions are better described by the latter.  Consequences of agent decisions to pursue interactions can depend on attributes at multiple levels, and decisions that maximize agent objectives may be in conflict with those of others or with beneficial outcomes for the network as a whole.  In humans and non-human animals, opportunities for interaction are constrained by factors such as location and mobility.  Social networks frequently involve a small number of agents, and stochastic processes are likely to be important influences on network dynamics.  Key emerging problems include how to incorporate multilayer and momentary data into network models, the roles of feedbacks between space use and network processes, how individual decisions interact with the evolution of network attributes, and the fitness or other consequences of such behaviors.  

This workshop will consider these emerging problems with an interdisciplinary approach incorporating modeling and empirical work from the social sciences, behavioral biology, mathematics, and statistics. In addition, because many of the challenges inherent to the study of social network dynamics are not unique to such networks, this workshop aims to include perspectives from other areas of network research. 

 

This MBI workshop is being co-sponsored by the National Institute of Statistical Sciences.

 

Accepted Speakers

Dena Asta
Benjamin Bolduc
Microbiology, The Ohio State University
Catherine Calder
Statistics, The Ohio State University
Benjamin Campbell
Political Science, The Ohio State University
Gerald Carter
Evolution, Ecology, and Organismal Biology, 300 Aronoff Lab
Skyler Cranmer
Political Science, The Ohio State University
Ian Hamilton
EEOB/Mathematics, The Ohio State University
Dana Haynie
Jennifer Hellmann
Animal Biology, University of Illinois at Urbana-Champaign
John Light
Facundo Memoli
math, The Ohio State University
Subhadeep Paul
Statistics, The Ohio State University
David Sivakoff
Statistics and Mathematics, The Ohio State University
Keith Warren
Social Work, The Ohio State University
Wednesday, November 7, 2018
Time Session
12:00 PM
01:00 PM

Lunch and Participant Collaboration

01:00 PM
01:30 PM

Introductory Remarks and Remarks by the Dean

01:30 PM
02:30 PM
Gerald Carter
02:30 PM
03:30 PM
Benjamin Campbell
03:30 PM
04:30 PM
Dena Asta
Thursday, November 8, 2018
Time Session
08:00 AM
09:00 AM

Breakfast and Daily Introduction

09:00 AM
10:00 AM
Skyler Cranmer - A Consistent Organizational Structure Across Multiple Functional Subnetworks of the Human Brain

A recurrent theme of both cognitive neuroscience and network neuroscience is that the brain has a consistent subnetwork structure that maps onto functional specialization for different cognitive tasks, such as vision, motor skills, and attention. Understanding how regions in these subnetworks relate is thus crucial to understanding the emergence of critical cognitive processes. However, the organizing principles that guide how regions within subnetworks communicate, and whether there is a common set of principles across subnetworks, remains unclear. This is partly due to available tools not being suited to precisely quantify the role that different organizational principles play in the organization of a subnetwork. Here, we apply the recently-developed correlation generalized exponential random graph model (cGERGM) to more completely quantify subnetwork structure. The cGERGM models a correlation network, such as those given in functional connectivity, as a function of activation motifs -- consistent patterns of coactivation (i.e., connectivity) between collections of nodes that describe how the regions within a network are organized (e.g., clustering) -- and anatomical properties -- relationships between the regions that are dictated by anatomy (e.g., Euclidean distance). Across nine functional subnetworks, we find remarkably consistent organizational properties guiding subnetwork architecture, suggesting a fundamental organizational basis for subnetwork communication. Specifically, all subnetworks displayed greater clustering than would be expected by chance, but lower preferential attachment (i.e., hub use), suggesting that human functional subnetworks follow a segregated highway structure rather than the small-world structure found in the whole-brain.

10:00 AM
11:00 AM
Kezia Manlove
11:00 AM
12:00 PM
Catherine Calder
12:00 PM
01:00 PM

Lunch and Participant Collaboration

01:00 PM
02:00 PM
Jennifer Hellmann
02:00 PM
03:00 PM
Facundo Memoli - Stable Signatures for Dynamic Networks via Zigzag Persistence

When studying flocking/swarming behaviors in animals one is interested in quantifying and comparing the dynamics of the clustering induced by the coalescence and disbanding of animals in different groups. In a similar vein, studying the dynamics of social networks leads to the problem of characterizing groups/communities as they form and disperse throughout time.

Motivated by this, we study the problem of obtaining persistent homology based summaries of time-dependent data. Given a finite dynamic graph (DG), we first construct a zigzag persistence module arising from linearizing the dynamic transitive graph naturally induced from the input DG. Based on standard results, we then obtain a persistence diagram or barcode from this zigzag persistence module. We prove that these barcodes are stable under perturbations in the input DG under a suitable distance between DGs that we identify.

More precisely, our stability theorem can be interpreted as providing a lower bound for the distance between DGs. Since it relies on barcodes, and their bottleneck distance, this lower bound can be computed in polynomial time from the DG inputs.

Along the way, we propose a summarization of dynamic graphs that captures their time-dependent clustering features which we call formigrams. These set-valued functions generalize the notion of dendrogram, a prevalent tool for hierarchical clustering. In order to elucidate the relationship between our distance between two DGs and the bottleneck distance between their associated barcodes, we exploit recent advances in the stability of zigzag persistence due to Botnan and Lesnick, and to Bjerkevik.

This is joint work with Woojin Kim.

https://research.math.osu.edu/networks/formigrams/

03:00 PM
04:00 PM

Scott Duxbury

Friday, November 9, 2018
Time Session
08:00 AM
09:00 AM

Breakfast and Daily Introduction

09:00 AM
10:00 AM
Subhadeep Paul - Community detection with realistic network models: a superimposed SBM and a hyperbolic space model

Detecting communities or a group of vertices that are similar to each other in a complex network is a well-studied problem in network science. Methods for community detection include model-based approaches, namely, based on the stochastic block model and its variants, latent space models, as well as model-free approaches including spectral, modularity and matrix factorization methods. The stochastic block model is the most commonly employed model of complex networks with community structure. However, the model fails to explain many observed properties of networks including, heterogeneous and power-law degree distribution (scale-free), strong local clustering especially triadic closures (transitivity) in an otherwise sparse graph, hierarchical nature of connections (core-periphery structure). The goals of this project are to develop models for networks with community structure that explain observed properties of real-world networks better. We propose a superimposed stochastic block model (SupSBM) and a hyperbolic latent space network community model (Hypcomm) for this purpose. We analyze the performance of a higher-order spectral clustering algorithm under the SupSBM. We also develop computationally efficient Variational EM, and Laplacian spectral embedding algorithms to estimate the latent positions and the communities in the Hypcomm model.

10:00 AM
11:00 AM
David Sivakoff
11:00 AM
12:00 PM
Benjamin Bolduc
12:00 PM
01:00 PM

Lunch and Participant Collaboration

01:00 PM
02:00 PM
Elizabeth Hobson
02:00 PM
03:00 PM
John Light
Name Email Affiliation
Bayer, Joseph bayer.66@osu.edu School of Communication, The Ohio State University
Bolduc, Benjamin bolduc.10@osu.edu Microbiology, The Ohio State University
Calder, Catherine calder.13@osu.edu Statistics, The Ohio State University
Campbell, Benjamin campbell.1721@osu.edu Political Science, The Ohio State University
Carter, Gerald ggc.bats@gmail.com Evolution, Ecology, and Organismal Biology, 300 Aronoff Lab
Cranmer, Skyler cranmer.12@osu.edu Political Science, The Ohio State University
Doogan, Nathan nathan.doogan@osumc.edu Ohio Colleges of Medicine Government Resource Center, The Ohio State University
Guerrero Montero, Deyssi guerreromontero.1@osu.edu Electrical & Computer Engr., The Ohio State University
Hamilton, Ian hamilton.598@osu.edu EEOB/Mathematics, The Ohio State University
Hamilton, Matthew hamilton.1323@osu.edu Sch of Environ & Natural Res, The Ohio State University
Hellmann, Jennifer jehellmann45@gmail.com Animal Biology, University of Illinois at Urbana-Champaign
Islam, Md rafiul.islam@ttu.edu Mathematics and Statistics, Texas Tech University
Kim, Woojin kim.5235@osu.edu Mathematics, The Ohio State University
Manlove, Kezia kezia.manlove@gmail.com Wildland Resources, Utah State University
Memoli, Facundo memoli@math.osu.edu math, The Ohio State University
Paul, Subhadeep paul.963@osu.edu Statistics, The Ohio State University
Sivakoff, David sivakoff.2@osu.edu Statistics and Mathematics, The Ohio State University
Warren, Keith warren.193@osu.edu Social Work, The Ohio State University
A Consistent Organizational Structure Across Multiple Functional Subnetworks of the Human Brain

A recurrent theme of both cognitive neuroscience and network neuroscience is that the brain has a consistent subnetwork structure that maps onto functional specialization for different cognitive tasks, such as vision, motor skills, and attention. Understanding how regions in these subnetworks relate is thus crucial to understanding the emergence of critical cognitive processes. However, the organizing principles that guide how regions within subnetworks communicate, and whether there is a common set of principles across subnetworks, remains unclear. This is partly due to available tools not being suited to precisely quantify the role that different organizational principles play in the organization of a subnetwork. Here, we apply the recently-developed correlation generalized exponential random graph model (cGERGM) to more completely quantify subnetwork structure. The cGERGM models a correlation network, such as those given in functional connectivity, as a function of activation motifs -- consistent patterns of coactivation (i.e., connectivity) between collections of nodes that describe how the regions within a network are organized (e.g., clustering) -- and anatomical properties -- relationships between the regions that are dictated by anatomy (e.g., Euclidean distance). Across nine functional subnetworks, we find remarkably consistent organizational properties guiding subnetwork architecture, suggesting a fundamental organizational basis for subnetwork communication. Specifically, all subnetworks displayed greater clustering than would be expected by chance, but lower preferential attachment (i.e., hub use), suggesting that human functional subnetworks follow a segregated highway structure rather than the small-world structure found in the whole-brain.

A Consistent Organizational Structure Across Multiple Functional Subnetworks of the Human Brain

A recurrent theme of both cognitive neuroscience and network neuroscience is that the brain has a consistent subnetwork structure that maps onto functional specialization for different cognitive tasks, such as vision, motor skills, and attention. Understanding how regions in these subnetworks relate is thus crucial to understanding the emergence of critical cognitive processes. However, the organizing principles that guide how regions within subnetworks communicate, and whether there is a common set of principles across subnetworks, remains unclear. This is partly due to available tools not being suited to precisely quantify the role that different organizational principles play in the organization of a subnetwork. Here, we apply the recently-developed correlation generalized exponential random graph model (cGERGM) to more completely quantify subnetwork structure. The cGERGM models a correlation network, such as those given in functional connectivity, as a function of activation motifs -- consistent patterns of coactivation (i.e., connectivity) between collections of nodes that describe how the regions within a network are organized (e.g., clustering) -- and anatomical properties -- relationships between the regions that are dictated by anatomy (e.g., Euclidean distance). Across nine functional subnetworks, we find remarkably consistent organizational properties guiding subnetwork architecture, suggesting a fundamental organizational basis for subnetwork communication. Specifically, all subnetworks displayed greater clustering than would be expected by chance, but lower preferential attachment (i.e., hub use), suggesting that human functional subnetworks follow a segregated highway structure rather than the small-world structure found in the whole-brain.

Disrupting Darknet Drug Markets

Interconnected systems in physical, biological, and social sciences are often at risk of attacks from exogenous sources. As a result, a growing number of studies focus on network attack tolerance. In general, this body of research assumes that damage to cross-sectional networks persists over time and has almost ubiquitously focused on attack strategies targeting integral vertices or edges. At issue, however, is that many networks are dynamic, especially in the social sciences, and capable of adaptive responses to attacks. Relatedly, network attack strategies may be diffuse, targeting an array of weak links, rather than high profile vertices. Together, these two omissions limit researchers’ ability to reach firm conclusions or derive policy recommendations from past research. Expanding on this prior work, we examine data collected from an online drug trafficking network comprised of roughly 7,400 actors and 17,000 drug transactions observed over 14 months. We use these data to develop an agent-based simulation experiment evaluating how the drug trafficking network responds to diffuse attacks. Results show that the network suffers substantial damage from diffuse attacks and that conventional methods for evaluating network robustness do a poor job of representing this type of damage. In particular, cross-sectional measures of network robustness in the simulated output networks suggest that the networks actually grow stronger in the aftermath of a diffuse attack, despite losing a substantial portion of edges and vertices. Pertinent to policy, these results indicate that the diffuse attack strategy evaluated in this study is an effective tactic for curbing online drug trafficking—an issue which has vexed law enforcement for some time.

Stable Signatures for Dynamic Networks via Zigzag Persistence

When studying flocking/swarming behaviors in animals one is interested in quantifying and comparing the dynamics of the clustering induced by the coalescence and disbanding of animals in different groups. In a similar vein, studying the dynamics of social networks leads to the problem of characterizing groups/communities as they form and disperse throughout time.

Motivated by this, we study the problem of obtaining persistent homology based summaries of time-dependent data. Given a finite dynamic graph (DG), we first construct a zigzag persistence module arising from linearizing the dynamic transitive graph naturally induced from the input DG. Based on standard results, we then obtain a persistence diagram or barcode from this zigzag persistence module. We prove that these barcodes are stable under perturbations in the input DG under a suitable distance between DGs that we identify.

More precisely, our stability theorem can be interpreted as providing a lower bound for the distance between DGs. Since it relies on barcodes, and their bottleneck distance, this lower bound can be computed in polynomial time from the DG inputs.

Along the way, we propose a summarization of dynamic graphs that captures their time-dependent clustering features which we call formigrams. These set-valued functions generalize the notion of dendrogram, a prevalent tool for hierarchical clustering. In order to elucidate the relationship between our distance between two DGs and the bottleneck distance between their associated barcodes, we exploit recent advances in the stability of zigzag persistence due to Botnan and Lesnick, and to Bjerkevik.

This is joint work with Woojin Kim.

https://research.math.osu.edu/networks/formigrams/

Community detection with realistic network models: a superimposed SBM and a hyperbolic space model

Detecting communities or a group of vertices that are similar to each other in a complex network is a well-studied problem in network science. Methods for community detection include model-based approaches, namely, based on the stochastic block model and its variants, latent space models, as well as model-free approaches including spectral, modularity and matrix factorization methods. The stochastic block model is the most commonly employed model of complex networks with community structure. However, the model fails to explain many observed properties of networks including, heterogeneous and power-law degree distribution (scale-free), strong local clustering especially triadic closures (transitivity) in an otherwise sparse graph, hierarchical nature of connections (core-periphery structure). The goals of this project are to develop models for networks with community structure that explain observed properties of real-world networks better. We propose a superimposed stochastic block model (SupSBM) and a hyperbolic latent space network community model (Hypcomm) for this purpose. We analyze the performance of a higher-order spectral clustering algorithm under the SupSBM. We also develop computationally efficient Variational EM, and Laplacian spectral embedding algorithms to estimate the latent positions and the communities in the Hypcomm model.