More Like this

1. Online Factorization and Partition of Complex Networks by Random Walk

   Yang, Lin; Yu, Zheng; Braverman, Vladimir; Zhao, Tuo; Wang, Mengdi (July 2019, Conference on Uncertainty and Artificial Intelligence)

   Finding the reduced-dimensional structure is critical to understanding complex networks. Existing approaches such as spectral clustering are applicable only when the full network is explicitly observed. In this paper, we focus on the online factorization and partition of implicit large lumpable networks based on observations from an associated random walk. We formulate this into a nonconvex stochastic factorization problem and propose an efficient and scalable stochastic generalized Hebbian algorithm (GHA). The algorithm is able to process random walk data in a streaming fashion and learn a low-dimensional representation for each vertex. By applying a diffusion approximation analysis, we show that the continuous-time limiting process of the stochastic algorithm converges globally to the “principal components” of the Markov chain. We also establish a finite-sample error bound that matches the nonimprovable state-of-art result for online factorization. Once learned the low-dimensional state representations, we further apply clustering techniques to recover the network partition. We show that when the associated Markov process is lumpable, one can recover the partition exactly with high probability given sufficient data. We apply the proposed approach to model the traffic flow of Manhattan as city-wide random walks. By using our algorithm to analyze the taxi trip data, we discover a latent partition of the Manhattan city that closely matches the traffic dynamics. 

   more » « less
2. Strongly interacting photonic quantum walk using single atom beamsplitters

   https://doi.org/10.1103/PhysRevResearch.6.013245  

   Zheng, Xinyuan; Waks, Edo (March 2024, Physical Review Research)

   Photonics provide an efficient way to implement quantum walks, the quantum analog of classical random walks, which demonstrate rich physics with potential applications. However, most photonic quantum walks do not involve photon interactions, which limits their potential to explore strongly correlated many-body physics of light. We propose a strongly interacting discrete-time photonic quantum walk using a network of single atom beamsplitters. We calculate output statistics of the quantum walk for the case of two photons, which reveals the strongly correlated transport of photons. Particularly, the walk can exhibit either bosonlike or fermionlike statistics which is tunable by postselecting the two-photon detection time interval. Also, the walk can sort different types of two-photon bound states into distinct pairs of output ports under certain conditions. These unique phenomena show that our quantum walk is an intriguing platform to explore strongly correlated quantum many-body states of light. Finally, we propose an experimental realization based on time-multiplexed synthetic dimensions. 

   more » « less
3. Simulating Random Walks in Random Streams

   https://doi.org/10.1137/1.9781611977073.120  

   Kallaugher, J; Kapralov, M; Price, E (January 2022, Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms)

   The random order graph streaming model has received significant attention recently, with problems such as matching size estimation, component counting, and the evaluation of bounded degree constant query testable properties shown to admit surprisingly space efficient algorithms. The main result of this paper is a space efficient single pass random order streaming algorithm for simulating nearly independent random walks that start at uniformly random vertices. We show that the distribution of k-step walks from b vertices chosen uniformly at random can be approximated up to error ∊ per walk using  words of space with a single pass over a randomly ordered stream of edges, solving an open problem of Peng and Sohler [SODA '18]. Applications of our result include the estimation of the average return probability of the k-step walk (the trace of the kth power of the random walk matrix) as well as the estimation of PageRank. We complement our algorithm with a strong impossibility result for directed graphs. 

   more » « less
4. Local Access to Random Walks , January 2022

   Biswas, A.S.; Pyne, E.; Rubinfeld, R. (January 2022, Innovations in Theoretical Computer Science (ITCS 2022))

   For a graph G on n vertices, naively sampling the position of a random walk of at time t requires work Ω(t). We desire local access algorithms supporting positionG(t) queries, which return the position of a random walk from some fixed start vertex s at time t, where the joint distribution of returned positions is 1/ poly(n) close to those of a uniformly random walk in ℓ1 distance. We first give an algorithm for local access to random walks on a given undirected d-regular graph with eO( 1 1−λ √ n) runtime per query, where λ is the second-largest eigenvalue of the random walk matrix of the graph in absolute value. Since random d-regular graphs G(n, d) are expanders with high probability, this gives an eO(√ n) algorithm for a graph drawn from G(n, d) whp, which improves on the naive method for small numbers of queries. We then prove that no algorithm with subconstant error given probe access to an input d-regular graph can have runtime better than Ω(√ n/ log(n)) per query in expectation when the input graph is drawn from G(n, d), obtaining a nearly matching lower bound. We further show an Ω(n1/4) runtime per query lower bound even with an oblivious adversary (i.e. when the query sequence is fixed in advance). We then show that for families of graphs with additional group theoretic structure, dramatically better results can be achieved. We give local access to walks on small-degree abelian Cayley graphs, including cycles and hypercubes, with runtime polylog(n) per query. This also allows for efficient local access to walks on polylog degree expanders. We show that our techniques apply to graphs with high degree by extending or results to graphs constructed using the tensor product (giving fast local access to walks on degree nϵ graphs for any ϵ ∈ (0, 1]) and Cartesian product. 

   more » « less
5. Virtual Gemba Analytics for Experiential Learning

   Santos, Fabiana; Mello, Alice; James, Nikki (January 2021, Proceedings 11th International Conference on Learning Analytics & Knowledge (LAK21))

   null (Ed.)

   When developing a project, input from stakeholders is a key to success. In this paper, a Virtual Gemba Walk dashboard for virtual capstone projects is proposed. A Virtual Gemba Walk aligns the expectations of the three stakeholders: student, teacher and industry sponsor through a real-time analytics dashboard that visualizes project indicators, tracks progress and identifies misaligned expectations. This poster presents a proposed interactive dashboard, that leverages data from technology to support the Virtual Gemba Walk process. The dashboard contains key indicators of the capstone project, triggers new Gemba Walks and visualizes feedback from each stakeholders’ perspective. The aim is to help students, teachers and industry sponsors to get meaningful feedback for a better chance of project success. 

   more » « less