Designing efficient and distributed algorithms has been central to almost all large networked systems. Examples include crawling-based sampling of large online social networks, statistical estimation or inference from massive scale of networked data, and distributed scheduling algorithms leading to maximal throughput and smaller delay in multihop wireless networks. At the heart of all such distributed and randomized algorithms lies the design of some version of a Markov chain such that (i) it possesses any desired stationary distribution, (ii) its transition probabilities depend only on locally available information on the fly with no or minimal amount of communication/computational overheads, and (iii) the chain itself converges fast (fast-mixing) or `efficient’. In particular, Markov Chain Monte Carlo (MCMC)-based approaches have proved to be extremely useful in building distributed network algorithms with near-optimal performance in various settings. 

In this talk,  I will present our recent work on sampling directed graphs for which none of the existing MCMC approaches applies. We have developed a framework for directed graphs called Non-Markovian Monte Carlo (NMMC) by establishing a mapping to convert a desired target distribution into the quasi-stationary distribution (QSD) of a carefully constructed transient Markov chain on an extended state space. As an application, we demonstrate how to achieve any given distribution on a directed graph and estimate the eigenvector centrality using a set of non-Markovian, history-dependent random walks on the same graph in a distributed manner. This is based on our recent paper, “Non-Markovian Monte Carlo on Directed Graphs”, to be presented in ACM Sigmetrics 2019.

 Do Young Eun received his Ph.D. degree from Purdue University, West Lafayette, IN, in 2003. Since August 2003, he has been with the Department of Electrical and Computer Engineering at North Carolina State University, Raleigh, NC, where he is currently a professor. His research interests include network modeling and performance analysis, mobile ad-hoc/sensor networks, mobility modeling, graph sampling, and randomized algorithms for large (social and wireless) networks. He has been a member of Technical Program Committee of various conferences including IEEE INFOCOM, ACM MobiHoc, and ACM Sigmetrics. He served on the editorial board of IEEE/ACM Transactions on Networking and Computer Communications Journal, and was TPC co-chair of WASA'11. He received the Best Paper Awards in the IEEE ICCCN 2005, IEEE IPCCC 2006, and IEEE NetSciCom 2015, and the National Science Foundation CAREER Award 2006. He supervised and co-authored a paper that received the Best Student Paper Award in ACM MobiCom 2007.