Mean Field Behavior of Random Networks and Systems

Ravi R. Mazumdar

University Research Chair Professor University of Waterloo, Canada

ABSTRACT

This talk will highlight the use of mean-field techniques that help in the analysis of complex interacting stochastic models. To highlight their use I will discuss two different classes of problems. The first their use in the context of load balancing among a large number of servers in order to minimize the latency or sojourn of jobs in the servers. I will begin by discussing the classical randomized Join the Shortest Queue (JSQ) where an incoming job is routed to the server with the least number of on-going jobs based on a finite random sample of servers. Mean field techniques are useful from two pounts of view: the first is that they enable us to obtain insights on the stationary occupancy distributions at an arbitrary server, and the second is that we can show that in large systems with processor sharing the stationary distribution is insensitive to the job length distribution. In my talk I will consider more general policies in which SQ(d) is a special case and show insensitivity carries over when sysytems are large while insensitivity does not hold in small systems.

Next I will discuss an application motivated by information dissemination in social networks with inter- actions among a large number of users. We consider a network of interacting agents where each agent exists in one of two possible states {0, 1} and the agents update their states through local interactions. We assume that agents in different states show different propensity towards updating their states( the acceptance of influence). In particular, through such a mechanism we can model the presence of stubborn agents that are not affected by interactions.

We will consider majority rule based opinion dynamics with many agents. This is modeled as follows: each node in state i ∈ {0,1} considers updating its state with probability pi and retains its state with probability 1 − pi at the points of a unit rate Poisson process. In case it decides to update its state it does so by following a majority rule based on randomly sampling two or more other nodes from the network and observing their states. If there is no clear majority, then the agent decides to switch its state with probabilitypf and retain it with probability 1 − pf . We analyze the evolution of the system in the mean field limit. We show that when pf ̸= 0 the equilibrium fraction of agents in each state does not depend on the initial population. We further analyze the case where pf = 0 that leads to consensus. We show that the consensus time scales as lnn, where n denotes the number of agents. We also study the situation where there are stubborn agents who do not change their opinion. This can result in metastability in that the network can oscillate between multiple stable equilibria.

The analysis is via mean field methods.

This work is with Thirupathiah Vasantam (Waterloo) , Arpan Mukhopadhyay (EPFL, Warwick) and Rahul Roy (ISI, New Delhi).

Biography: The speaker was educated at the Indian Institute of Technology, Bombay (B.Tech, 1977), Imperial College, London (MSc, DIC, 1978) and obtained his PhD in Control Theory under A. V. Balakrishnan at UCLA in 1983.

He is currently a University Research Chair Professor in the Dept. of ECE at the University of Waterloo, Ont., Canada where he has been since September 2004. He has served on the faculties of Columbia University (NY), INRS- Telecommunications (University of Quebec), the University of Essex (UK) and Purdue University (USA). Since 2012 he is a D.J. Gandhi Distinguished Visiting Professor at the Indian Institute of Technology, Bombay, India. He is a Fellow of the IEEE and the Royal Statistical Society. His is the recipient of best paper awards at INFOCOM 2006 , the ITC-27 2015, Performance 2015, and a finalist at INFOCOM 1998. He is the author of a monograph entitledPerformance Modeling, Stochastic Networks, and Statistical Multiplexing published by Morgan and Claypool, San Francisco in 2013.

His research interests are in stochastic modelling and analysis applied to complex networks and systems, and in issues of network science.