Link Prediction in Graph Streams
Authors: Charu Aggarwal, Peixiang Zhao, Gewen He
Liked by: Maximimi
Domains: Dynamic graph
Tags: ICDE2016
Uploaded by: Maximimi
Upload date: 2018-08-22 13:16:13

Comments:

### Concerns: - It seems that the method needs to store $L$ integers per node. That is a total of $N*L$ integers while storing the graph requires $2*M$ integers (where $M$ is the number of edges), thus the method is useful only if $L<2*M/N$ (that is if $L$ smaller than the average degree). In the experiments, the average degree of the three graphs is approximately 7, 55 and 42, while $L$ is 50 or 80. There is thus no gain in space compared to a good implementation of a straightforward algorithm storing the full graph. - Once the sketch for each node is obtained, it is not clear how to obtain each relevant pair of nodes and its similarity. It seems that each possible pair of nodes has to be considered which is very under-optimal and not scalable. - Each graph used in the experiments easily fits in the RAM of any commodity machine. For such small graphs, an exact method storing the full graph should be faster in practice. ### Alternative approach: https://github.com/maxdan94/NeighSim
Maximimi at 2018-08-22 13:44:24
Edited by Maximimi at 2018-08-31 18:24:10

You comment anonymously! You will not be able to edit/delete the comment.

Please consider to register or login.

Use $\LaTeX$ to type formulæ and markdown to format text.
When you post something to which you hold the copyright you authorise us to do distribute this data across the scientific community. All data you give us will be freely available online. You can post any public domain content. Please see this page to learn more about us, Papersγ's terms of use and privacy policy.