"Classical and Quantum Random-Walk Centrality Measures in Multilayer Networks"

Another paper of mine just came out in final form. Here are some details about it.

Title: Classical and Quantum Random-Walk Centrality Measures in Multilayer Networks

Authors: Lucas Böttcher and Mason A. Porter

Abstract: Multilayer network analysis is a useful approach for studying networks of entities that interact with each other via multiple relationships. Classifying the importance of nodes and node-layer tuples is an important aspect of the study of multilayer networks. To do this, it is common to calculate various centrality measures, which allow one to rank nodes and node-layers according to a variety of structural features. In this paper, we formulate occupation, PageRank, betweenness, and closeness centralities in terms of node-occupation properties of different types of continuous-time classical and quantum random walks on multilayer networks. We apply our framework to a variety of synthetic and real-world multilayer networks, and we identify notable differences between classical and quantum centrality measures. Our computations give insights into the correlations between certain centralities that are based on random walks and associated centralities that are based on geodesic paths.

Tales from the ArXiv: Don't Feed Random Walkers After Midnight

There is a new paper on arXiv about reactive random walkers.

Quoting from the abstract: "The model is highly versatile, as the motion of the walkers can be fed on topological properties of the nodes..."

Comment: But don't feed them after midnight.

Tales from the ArXiv: "The Random Walk of Cars and Their Collision Probabilities with Planets"

Well, the title of this paper pretty much says it all.

However, there are also some choice quotes in the paper. For example, I really like this deadpan sentence: We now turn to the long-term dynamical evolution for which we integrate 240 realizations of the Tesla for 3.5 Myr into the future.

The final part of the abstract is also nice: By running a large ensemble of simulations with slightly perturbed initial conditions, we estimate the probability of a collision with Earth and Venus over the next one million years to be 6% and 2.5%, respectively. We estimate the dynamical lifetime of the Tesla to be a few tens of millions of years. (I guess the simulation of 3.5 million years wasn't long enough.)

(Tip of the cap to Predrag Cvitanovic.)

"Random Walks and Diffusion on Networks"

Our review article on random walks on networks has its final coordinates. Here are the details.

Title: Random Walks and Diffusion on Networks

Authors: Naoki Masuda, Mason A. Porter, and Renaud Lambiotte

Abstract: Random walks are ubiquitous in the sciences, and they are interesting from both theoretical and practical perspectives. They are one of the most fundamental types of stochastic processes; can be used to model numerous phenomena, including diffusion, interactions, and opinions among humans and animals; and can be used to extract information about important entities or dense groups of entities in a network. Random walks have been studied for many decades on both regular lattices and (especially in the last couple of decades) on networks with a variety of structures. In the present article, we survey the theory and applications of random walks on networks, restricting ourselves to simple cases of single and non-adaptive random walkers. We distinguish three main types of random walks: discrete-time random walks, node-centric continuous-time random walks, and edge-centric continuous-time random walks. We first briefly survey random walks on a line, and then we consider random walks on various types of networks. We extensively discuss applications of random walks, including ranking of nodes (e.g., PageRank), community detection, respondent-driven sampling, and opinion models such as voter models.

Special Guest Star: A very weary random walker

"A Local Perspective on Community Structure in Multilayer Networks"

One of my papers, which came out a few months ago, final got its final coordinates (page numbers, etc.). Here are the details.

Title: A Local Perspective on Community Structure in Multilayer Networks

Authors: Lucas G. S. Jeub, Michael W. Mahoney, Peter J. Mucha, and Mason A. Porter

Abstract: The analysis of multilayer networks is among the most active areas of network science, and there are several methods to detect dense “communities” of nodes in multilayer networks. One way to define a community is as a set of nodes that trap a diffusion-like dynamical process (usually a random walk) for a long time. In this view, communities are sets of nodes that create bottlenecks to the spreading of a dynamical process on a network. We analyze the local behavior of different random walks on multiplex networks (which are multilayer networks in which different layers correspond to different types of edges) and show that they have very different bottlenecks, which correspond to rather different notions of what it means for a set of nodes to be a good community. This has direct implications for the behavior of community-detection methods that are based on these random walks.

A Random Walk Through Public Broadcasting

A few days ago, PBS posted a video introducing random walks to a public audience! Sweet!

Update: This is an episode of a mathematics show called "Infinite Series". The above episode refers to an episode about Markov chains. Take a look at their YouTube channel and Twitter feed.

Tales from the ArXiv: Participants Viewing a Random Walk

My collaborator Dani Bassett has gotten a bit meta about community structure.

Here is a choice quote from their abstract: "How human learners exploit this information remains an essential question. Here, we focus on the temporal constraints that govern such a process. Participants viewed a continuous sequence of images generated by three distinct walks on a modular network."

This is a missed opportunity: They could have used the Zachary Karate Club for these experiments. (It's probably still worth writing up a short blurb about this paper for the Improbable Research blog.)

The Ranker Walker College Football Rankings are Back!

The random walker rankings for American college football are back. Take a look to see which teams the walkers "think" are the best ones.

Art: "The Random Walker Heads Off Into the Sunset"

I couldn’t stop thinking about my idea about an exhausted random walker leaving a network and retiring and heading off into the sunset, and I was able to get my former student Yulian Ng to draw it. Add a bit of text, and here is what we have.

"A Unified Theory of Randomness"

This article is very cool. It talks about some exciting work that follows up that of people like Wendelin Werner, Oded Schramm, Martin Hairer, and others. The younger author of the pair who are doing many of these great things seems like somebody who is going to be considered strongly for a Fields Medal. (The article doesn't mention this, but this does appear to be at that level.)

In fact, several recent Fields Medals have been awarded for work with deep relationships to statistical mechanics (and related topics like kinetic theory and probability theory), and it took quite some time for these to be considered "acceptable" mathematics topics.

A Hungry Random Walker

And now we have a hungry random walker model for chemotaxis, with some motivation from the game Pac-Man. Recall that I recently posted an entry about microorganism Pac-Man.

The Random Walker then Heads Towards the Hills

Here is a sign that you know you're tired: You are looking at a description of a random-walk model, and it looks like the text says "the walker then heads towards the hills". (It actually says "tills" rather than hills, as we're modeling shopper trajectories.)

But this gave me a wonderful mental picture of an exhausted random walker leaving a network in disgust and heading off towards the hills. My picture also has a sunset in it.

This Random Walk is Not One of the Usual Suspects

The random walk in the paper "The Spacey Random Walk: a Stochastic Process for Higher-order Data" is not one of the usual suspects.