Scalable Similarity Estimation in Social Networks: Closeness, Node Labels, and Random Edge Lengths

Edith Cohen, Daniel Delling, Fabian Fuchs, Moises Goldszmidt, Andrew V. Goldberg and Renato F. Werneck


Similarity estimation between nodes based on structural properties of graphs is a basic building block used in the analysis of massive networks for diverse purposes such as link prediction, product rec- ommendations, advertisement, collaborative filtering, and community discovery. While local similarity measures, based on proper- ties of immediate neighbors, are easy to compute, those relying on global properties have better recall. Unfortunately, this better qual- ity comes with a computational price tag. Aiming for both accuracy and scalability, we make several contributions. First, we define closeness similarity, a natural measure that compares two nodes based on the similarity of their relations to all other nodes. Second, we show how the all-distances sketch (ADS) node labels, which are efficient to compute, can support the estimation of closeness similarity and shortest-path (SP) distances in logarithmic query time. Third, we propose the randomized edge lengths (REL) technique and define the corresponding REL distance, which captures both path length and path multiplicity and therefore improves over the SP distance as a similarity measure. The REL distance can also be the basis of closeness similarity and can be estimated using SP computation or the ADS labels. We demonstrate the effectiveness of our measures and the accuracy of our estimates through experiments on social networks with up to tens of millions of nodes.

Guest: Daniel Delling (Microsoft Research)

Host: Chen Avin

Exact Distance Oracles for Planar Graphs

Shay Mozes and Christian Sommer


We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following:

  • Given a desired space allocation S \in \[ n \log\log n, n^2 \], we show how to construct in time a data structure of size O(S) that answers distance queries in time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever .
  • We provide a linear-space exact distance oracle for planar graphs with query time for any constant . This is the first such data structure with provable sublinear query time.
  • For edge lengths , we provide an exact distance oracle of space such that for any pair of nodes at distance the query time is . Comparable query performance had been observed experimentally but could not be proven.

Our data structures are based on the following new tool: given a non-self-crossing cycle C with nodes, we can preprocess G in time to produce a data structure of size that can answer the following queries in time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA’05), which reports distances to the boundary of a face, rather than a cycle.
The best distance oracles for planar graphs until the current work are due to Cabello (SODA’06), Djidjev (WG’96), and Fakcharoenphol and Rao (FOCS’01). For and space , we essentially improve the query time from to .

Guest: Shay Mozes
Host: Shantanu Das