Longest shortest path, Java, WebGraph
Jump to navigation
Jump to search
Primary author of this description: I.V.Afanasyev.
Contents
1 Links
WebGraph (class FourSweepIterativeFringeDiameter), multithreaded implementation. The algorithm was used to calculate the diameter of the subgraph of the social network Facebook (149 million vertices, 16 billion edges), running time was 20 minutes[1].
2 Locality of data and computations
2.1 Locality of implementation
2.1.1 Structure of memory access and a qualitative estimation of locality
2.1.2 Quantitative estimation of locality
3 Scalability of the algorithm and its implementations
3.1 Scalability of the algorithm
3.2 Scalability of of the algorithm implementation
4 Dynamic characteristics and efficiency of the algorithm implementation
5 Run results
6 References
- ↑ Backstrom, Lars, Paolo Boldi, Marco Rosa, Johan Ugander, and Sebastiano Vigna. “Four Degrees of Separation,” WebSci'12, 33–42, New York, New York, USA: ACM Press, 2012. doi:10.1145/2380718.2380723.
