Shortest Path Centrality and the All-pairs Shortest Paths Problem via Sample Complexity.
Alane M. de LimaMurilo V. G. da SilvaAndré Luís VignattiPublished in: CoRR (2019)
Keyphrases
- shortest path
- sample complexity
- betweenness centrality
- theoretical analysis
- shortest path problem
- social network analysis
- supervised learning
- pac learning
- special case
- learning problems
- learning algorithm
- vc dimension
- upper bound
- social networks
- active learning
- lower bound
- road network
- generalization error
- shortest path algorithm
- optimal path
- weighted graph
- training examples
- shortest distance
- average case
- high dimensional
- pairwise
- sample size
- machine learning algorithms
- semi supervised learning
- nearest neighbor
- small number
- flow graph
- training data