Evolutionary Graph Theory and Community Detection in Networks

Over the past two  years or so, I’ve been exploring various problems related to evolutionary graph theory and network science with my colleague Paulo Shakarian (now at ASU). I’m grateful for having had the opportunity to do this work with such a brilliant and hard-working colleague as Paulo and wanted to highlight some of it work here.

Evolutionary Graph Analytics

In the evolutionary graph theory work we studied diffusion in graphs or networks, inspired by the framework outlined by Martin Nowak in his book “Evolutionary Dynamics.” This framework of evolutionary graph theory is elegant and broadly applicable, whether to study diffusion in biological networks or to understand how the structure of human or technological social networks influence the spread and dynamics of cultural/social information and behavior. The basic idea is that, given a graph or network of nodes and edges connecting the nodes, ‘mutant’ nodes compete against ‘resident’ nodes via their connections which allow for the opportunity for nodes to ‘infect’ or spread their type to other nodes.

Relatedly, we’ve developed new analytical methods to quickly compute “fixation probabilities”, which is the probability that a ‘mutant’ node takes over the entire population of a given graph or network. We’ve also provided a rather comprehensive (to date) review of evolutionary graph theory and it’s applications within game theory. Here are the relevant publications:

Community Detection in Geo-Spatial Networks

Unrelated to evolutionary graph theory, we also studied the discovery of communities in networks. Specifically, we developed data mining algorithms that can be used to find communities within networks while considering geo-spatial characteristics in addition to the network connection structure. For instance, given a network of electronic communications, one might be interested in identifying communities that are geo-spatially distant, toto identify higher-level organizational structures. The following papers outline the approach: