An official website of the United States government
Abstract We present analytical results for the distribution of first return (FR) times of non-backtracking random walks (NBWs) on undirected configuration model networks consisting of $$N$$ nodes with degree distribution $P(k)$. We focus on the case in which the network consists of a single connected component. Starting from a random initial node $$i$$ at time $t=0$, an NBW hops into a random neighbor of $$i$$ at time $t=1$ and at each subsequent step it continues to hop into a random neighbor of its current node, excluding the previous node. We calculate the tail distribution $$P ( T_{\rm FR} > t )$$ of first return times from a random initial node to itself. It is found that $$P ( T_{\rm FR} > t )$$ is given by a discrete Laplace transform of the degree distribution $P(k)$. This result exemplifies the relation between structural properties of a network, captured by the degree distribution, and properties of dynamical processes taking place on the network. Using the tail-sum formula, we calculate the mean first return time $${\mathbb E}[ T_{\rm FR} ]$$. Surprisingly, $${\mathbb E}[ T_{\rm FR} ]$$ coincides with the result obtained from Kac's lemma that applies to simple random walks (RWs). We also calculate the variance $${\rm Var}(T_{\rm FR})$$, which accounts for the variability of first return times between different NBW trajectories. We apply this formalism to Erd{\H o}s-R\'enyi networks, random regular graphs and configuration model networks with exponential and power-law degree distributions and obtain closed-form expressions for $$P( T_{\rm FR} > t )$$ as well as its mean and variance. These results provide useful insight on the advantages of NBWs over simple RWs in network exploration, sampling and search processes.
more »
« less
Attributed Random Walk as Matrix Factorization
Mainstream random walks on graphs mostly focus on the topology while ignoring node attributes. In this paper, we develop a matrix form of the attributed random walk with pointwise mutual information in an unsupervised fashion. We show through experiments that the generated embeddings of flexible dimensions are robust to label missing on the transductive node classification task.
more »
« less
- PAR ID:
- 10159689
- Date Published:
- Journal Name:
- neural information processing systems, graph representation learning workshop
- ISSN:
- 1049-5258
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We propose an interdependent random geometric graph (RGG) model for interdependent networks. Based on this model, we study the robustness of two interdependent spatially embedded networks where interdependence exists between geographically nearby nodes in the two networks. We study the emergence of the giant mutual component in two interdependent RGGs as node densities increase, and define the percolation threshold as a pair of node densities above which the giant mutual component first appears. In contrast to the case for a single RGG, where the percolation threshold is a unique scalar for a given connection distance, for two interdependent RGGs, multiple pairs of percolation thresholds may exist, given that a smaller node density in one RGG may increase the minimum node density in the other RGG in order for a giant mutual component to exist. We derive analytical upper bounds on the percolation thresholds of two interdependent RGGs by discretization, and obtain 99% confidence intervals for the percolation thresholds by simulation. Based on these results, we derive conditions for the interdependent RGGs to be robust under random failures and geographical attacks.more » « less
-
We consider the problem of inferring the conditional independence graph (CIG) of a high-dimensional stationary, multivariate long-range dependent (LRD) Gaussian time series. In a time series graph, each component of the vector series is represented by a distinct node, and associations between components are represented by edges between the corresponding nodes. In a recent work on graphical modeling of short-range dependent (SRD) Gaussian time series, the problem was cast as one of multi-attribute graph estimation for random vectors where a vector is associated with each node of the graph. At each node, the associated random vector consists of a time series component and its delayed copies. A theoretical analysis based on short-range dependence has been given in Tugnait (2022 ICASSP). In this paper we analyze this approach for LRD Gaussian time series and provide consistency results regarding convergence in the Frobenius norm of the inverse covariance matrix associated with the multi-attribute graph.more » « less
-
We consider the problem of inferring the conditional independence graph (CIG) of a high-dimensional stationary multivariate Gaussian time series. In a time series graph, each component of the vector series is represented by distinct node, and associations between components are represented by edges between the corresponding nodes. We formulate the problem as one of multi-attribute graph estimation for random vectors where a vector is associated with each node of the graph. At each node, the associated random vector consists of a time series component and its delayed copies. We present an alternating direction method of multipliers (ADMM) solution to minimize a sparse-group lasso penalized negative pseudo log-likelihood objective function to estimate the precision matrix of the random vector associated with the entire multi-attribute graph. The time series CIG is then inferred from the estimated precision matrix. A theoretical analysis is provided. Numerical results illustrate the proposed approach which outperforms existing frequency-domain approaches in correctly detecting the graph edges.more » « less
-
We consider the problem of inferring the conditional independence graph (CIG) of high-dimensional Gaussian vectors from multi-attribute data. Most existing methods for graph estimation are based on single-attribute models where one associates a scalar random variable with each node. In multi-attribute graphical models, each node represents a random vector. In this paper we consider a sparse-group smoothly clipped absolute deviation (SG-SCAD) penalty instead of sparse-group lasso (SGL) penalty to regularize the problem. We analyze an SG-SCAD-penalized log-likelihood based objective function to establish consistency of a local estimator of inverse covariance. A numerical example is presented to illustrate the advantage of SG-SCAD-penalty over the usual SGL-penalty.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Conference Paper:
- The DOI is not currently available.
