Algorithms, Models, and Mining

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

Affiliated Faculty

Computer Science

Analysis and modeling of dynamic processes in networks.

Computer Science

Computer Science

Control theory, Multi-agent networks, Robotic coordination, Power systems

Geography

Network design, Transportation networks, Biological network conservation

Efficient algorithms

High-performance computation, Mathematical software, Graph algorithms

Mechanical Engineering

Computational science and engineering, numerical methods, dynamics and control, biological networks, power systems, robotic networks

Control theory, Distributed control, Modeling of biological networks

Image/video analysis, multimedia databases and data mining, steganography, and signal/image processing for bio-informatics.

Computer Science
NLP, Text Mining, Information Retrieval, Information and Code Theory, Linguistics, Graph Theory, Networks

Electrical and Computer Engineering

Ecology, Evolution, and Marine Biology

Algorithms for image synthesis, computational image processing, and computational photography

Director of Network Science IGERT
Network analysis, Data mining, Bioinformatics

Electrical and Computer Engineering

Graph algorithms

Computer Science

Human computer interaction, artificial intelligence, machine learning, and cognition, network science and big data

Geography

Media neuroscience, research methods and statistics

Data bases, Data mining