The last several decades have witnessed a remarkable growth in the algorithmic theory of networks, from combinatorial algorithms for shortest paths, network flows, cuts and partitions to models of random graphs, Internet, social graphs, biological networks, and the small-world phenomena. In part, this growth is a result of a highly beneficial feedback loop: algorithmic advances and theoretical insights into graphs have led to their widespread adoption by scientists and engineers as modeling tools, which in turn has posed new problems and led to better solutions. In this context, the rise of Big Data, and their unprecedented scale, is forcing a rethink of many of the algorithms and theories. Take for instance the example of a social graph such as Facebook. This network has about 900 million nodes, and billions of edges. On a graph of this scale, computing a single node-pair distance takes time in the order of minutes even using the simple hop count metric. The high level applications running on these graphs must perform millions of such queries. Thus, a grand challenge for researchers of tomorrow is to build algorithmic foundations and theories that can scale to networks with millions of nodes and billions of edges with millisecond response. Besides the scalability aspects, the other challenge is to understand the specific characteristics of social and biological networks, and the analyses of interest so that we can engineer algorithms to networks. The characteristics can be based on the static structure (is the network scale-free? is it modular?) and the dynamics (what is typical span and size of cascades? do they also satisfy scale-free behavior?). Can we develop algorithms whose worst-case bounds are exponential but perform well on networks that are scale-free and modular?

Dynamic networks are another topic of research under this focus area. Dynamic networks characterize traffic variation in transportation networks, variation of trade rates in a network of trading agents, and phases of pathway switching in gene interaction networks. The study of such dynamic networks and how information flows through them is essential to developing a theory of dynamic networks, just as the existing research has established a theory for static networks and their long-term evolution. The structure of dynamic graphs can change over a wide spectrum of time scales, ranging from microseconds (in fast fading wireless channels) to minutes (inter-linked blog posts) to days to years (social networks). We are developing a foundational theory of time-varying graphs, whose primary aim is to understand the evolution of temporal graph properties as a function of the evolving graph structure. We are investigating the short-term dynamics of networks by studying how information of different kinds flows, whether there are significant patterns of flow, how content affects flow and vice versa, what is the impact of structure on dynamics, and whether content and structure co-evolve. Finding effective solutions to these problems requires scalable data mining algorithms, development of control-theoretic models that can capture dynamics, and validation of the results on social and biological networks.

Related Training Modules

• M1: Spectral Analysis of Dynamic Graphs
• M2: Analysis of Topic Networks
• M3: Understanding Scalability of Distributed Estimation Algorithms
• M4: Analyzing the Connectome of C. elegans
• M6: Modeling Network Evolution in Metric Spaces
• M9: Determining Polarizing Entities and Opinions in Online Networks
• M10: Network Science of Teams
• M11: Symbolic Execution with a Graph Database
• M12: Network Stability in Food Webs
• M13: Modeling Rhetoric
• M14: An Empirical Analysis of Sexual Networks and Pregnancy in Ghana
• M15: Narrative (Counter-)Mobilizations in U.S. Same-Sex Marriage Struggle
• M16: Learning Path Generation
• M17: Models of Social Power Evolution
• M18: Speeding up graph processes on graphs embedded in latent spaces
• M19: A Privacy Model for Life Cycle Inventory Databases
• M20: Sociological Approach to Learning Path Generation
• M21: Epidemic Propagation Over Contact Networks
• M22: Information Networks in the Moral Narrative Analyzer (MoNA)
• M23: Approximate Nearest Neighbor Problem in High Dimensions with Constraints
• M26: Embedding a Network into Latent Space
• M27: Understanding and Modeling Complex Network Processes
• M28: Modeling Structural Balance in Networks
• M29: FLoRa Framework
• M30: General Framework for Learning Node Embeddings
• M31: Development of a Reader Network