A bag-of-paths framework for network data analysis
This work develops a generic framework, called the bag-of-paths (BoP), for link and network data analysis. The central idea is to assign a probability distribution on the set of all paths in a network. More precisely, a Gibbs-Boltzmann distribution is defined over a bag of paths in a network, that is, on a representation that considers all paths independently. We show that, under this distribution, the probability of drawing a path connecting two nodes can easily be computed in closed form by simple matrix inversion. This probability captures a notion of relatedness between nodes of the graph: two nodes are considered as highly related when they are connected by many, preferably low-cost, paths. As an application, two families of distances between nodes are derived from the BoP probabilities. Interestingly, the second distance family interpolates between the shortest path distance and the resistance distance. In addition, it extends the Bellman-Ford formula for computing the shortest path distance in order to integrate sub-optimal paths by simply replacing the minimum operator by the soft minimum operator. Experimental results on semi-supervised classification show that both of the new distance families are competitive with other state-of-the-art approaches. In addition to the distance measures studied in this paper, the bag-of-paths framework enables straightforward computation of many other relevant network measures.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
SPGNN-API: A Transferable Graph Neural Network for Attack Paths Identification and Autonomous Mitigation
Attack paths are the potential chain of malicious activities an attacker performs to compromise network assets and acquire privileges through exploiting network vulnerabilities. Attack path analysis helps organizations t…
Graph Neural NetworkLog-PDE Methods for Rough Signature Kernels
Signature kernels, inner products of path signatures, underpin several machine learning algorithms for multivariate time series analysis. For bounded variation paths, signature kernels were recently shown to solve a Gour…
Time SeriesTime Series AnalysisSpatial Clustering Approach for Vessel Path Identification
This paper addresses the challenge of identifying the paths for vessels with operating routes of repetitive paths, partially repetitive paths, and new paths. We propose a spatial clustering approach for labeling the vess…
ClusteringPositionWeakness Analysis of Cyberspace Configuration Based on Reinforcement Learning
In this work, we present a learning-based approach to analysis cyberspace configuration. Unlike prior methods, our approach has the ability to learn from past experience and improve over time. In particular, as we train …
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Discover the Hidden Attack Path in Multi-domain Cyberspace Based on Reinforcement Learning
In this work, we present a learning-based approach to analysis cyberspace security configuration. Unlike prior methods, our approach has the ability to learn from past experience and improve over time. In particular, as …
Reinforcement Learning (RL)