Decomposing Huge Networks into Skeleton Graphs by Reachable Relations
Abstract
The research team developed new techniques for accelerating critical link detection and distance-based centrality computation by decomposing huge networks into skeleton graphs by reachable relations. The main research results are in three new approaches, 1) efficient detection of critical links in a large network by using bottom-k sketch algorithm and by employing two new acceleration techniques: marginal-link updating and redundant-link skipping, 2) accurate and efficient detection of such critical links by a new method which consists of one existing and two new acceleration techniques: redundant-link skipping, marginal-node pruning and burn-out following, and 3)accelerating computation of distance-based closeness and betweenness centrality measures by pruning some nodes and links based on the cut links of a given spatial network.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 07, 2017
- Accession Number
- AD1044059
Entities
People
- Kazumi SaitÅ
Organizations
- University of Shizuoka