Complex Networks and their Analysis with Random Walks

Daniel Figueiredo (Federal University of Rio de Janeiro, Brazil) and Konstantin Avrachenkov (Inria Sophia Antipolis, France)

Summary:

Network Science has emerged as a field of study to comprehensively understand how physical and virtual artifacts are connected along with the implications of such connectedness. Networks (or graphs) serves as the ubiquitous mathematical abstraction to represent structure induced by a binary relationship. Such model has been widely applied to represent and study information networks (e.g., web pages and hyper-links), social networks (e.g., people and co-authorship), biological networks (e.g., proteins and interactions) and technological networks (e.g., airports and flights). Fueled by the increasingly availability of vast amounts of empirical data, networks with millions of nodes are being studied with the goal of understanding various aspects of their structure. For example, a promising feature of a network is its degree distribution, i.e. the fraction of nodes that have degree k, for k = 0, 1, … Network structure can reveal various aspects about nodes, such as their relative importance or their community structure. Centrality metrics such as PageRank and Betweeness impose an importance ordering among the set of nodes, while community detection metrics partitions the nodes into subsets. In this tutorial we will introduce the field of Network Science by first presenting empirical studies of networks and their main findings with respect to structural features. We will identify commonalities among different real networks, such as heavy-tailed degree distribution and short distances, present in Facebook friendship network and the Internet AS-level graph, for example. Besides presenting classical metrics for characterizing networks, such as degrees, distances and clustering, we will also introduce centrality metrics and community structure metrics. We then present and discuss mathematical models for networks, starting with the well-studied Erdos-Reyni (G(n, p)) model followed by BA (Barabási-Albert) model which embodies preferential attachment property and WS (Watts-Strogatz) model which embodies small-world properties.

In the context of network science, random walks emerges as an ubiquitous methodology to characterize and measure different aspects of network structure, in part due to its mathematical simplicity and well-understood properties. Typical questions in the analysis of large complex networks are how large is a network in terms of nodes and links? which nodes are most important/central? the degree distribution follows a power law? if yes, what is the exponent of the power law? how to estimate quickly the clustering coefficient? how to detect quickly principal clusters/communities of the network? All these questions can be answered with the help of the theory of random walks on graphs. In particular, using the theory of random walks on graphs, we can design algorithms with linear or even sublinear complexity. Such light complexity is necessary if we need to deal with networks of billions of nodes and links.

Outline:

• Networks abound: information, social, biological, and technological networks
• Characterization of real networks: degrees, distances, clustering, centrality, communities
• Models for networks: G(n, p), BA Model (preferential attachment), WS Model (small-world)
• Random walks: definition, variations and properties
• Characterization via random walks: sampling, centrality, communities

Biographies of the presenters:

Daniel Ratton Figueiredo received a BS cum laude degree in Computer Science and MSc degree in Computer and Systems Engineering from the Federal University of Rio de Janeiro (UFRJ) Brazil, in 1996 and 1999, respectively. He received a MSc and PhD degrees in Computer Science from the University of Massachusetts Amherst (UMass) in 2005. He worked as a post-doc researcher at the Swiss Federal Institute of Technology, Lausanne (EPFL). In 2007, he joined the Department of Computer and Systems Engineering (PESC/COPPE) at the Federal University of Rio de Janeiro (UFRJ), Brazil where he currently holds an associate professor position. In 2012 he was a visiting scholar in the School of Computer Science at the University of Massachusetts Amherst (UMass). He has a Research Productivity Fellowship granted by CNPq (since 2009) and is member of the Young Scientists Program granted by FAPERJ (since 2010). His main interests are in Network Science and Computer Networks, in particular modeling system dynamics in networks.

Konstantin Avrachenkov received Master degree with distinction in Control Theory from St. Petersburg State Polytechnic University (1996), the Ph.D. degree in Mathematics from University of South Australia (2000) and the Habilitation (Doctor of Science) from University of Nice Sophia Antipolis (2010). Currently, he is a Director of Research at Inria Sophia Antipolis, France. He is an associate editor of International Journal of Performance Evaluation and ACM Transactions on Modeling and Performance Evaluation of Computing Systems. His main research interests are Markov processes, singular perturbation theory, queueing theory, game theory and various applications in networks.