☆

1

## About scalability:
"We apply a standard cleaning procedure (for similarity) and remove high out-degrees. In other words, if some vertex v has more than 10K followers (outdegree > 10K), we remove
all these edges. (We do not remove the vertex, but rather only its out-edges.) Intuitively, the fact that two vertices are followed by v is not a useful signal for similarity. In
flock and friendster, such vertices are typically spammers and should be ignored. For webgraphs, a page linking to more than 10K other pages is probably not useful for similarity
measurement."
- Typo: should be "more than 10K followeEs (outdegree > 10K)" not "followers".
- Such a cleaning procedure makes sense, in addition, it has a valuable side effect: in practice, after applying such a cleaning procedure, many pairs of nodes with very small non-zero similarity (in the original directed graph) have a similarity of zero (in the new graph with the out-edges of the out-hubs removed).
- Given that such a cleaning procedure is applied, a brute force approach (that computes the similarity of each pair of nodes sharing at least one in-neighbor) is scalable to a large extent.
- The following C code and experiments support the previous claim: https://github.com/maxdan94/cosineSparseMatrix
- If scalability is still an issue, in-edges of nodes with very high in-degree could also be removed.
"In our example, this turns out to be more than 100 trillion triples. This is infeasible even for a large industrial-strength cluster.".
Listing 100 trillion triples seems doable with a medium-strength cluster.
"If a matrix A has a 100 billion non-zeroes, it takes upwards of 1TB just to store the entries. This is more than an order of magnitude of the storage of a commodity machine in a cluster. Any approach of partitioning A into submatrices cannot scale."
Indeed, memory seems to be a problem. However, it is unclear why an approach partitioning A into submatrices cannot scale.
## Dataset:
"The dataset friendster is a social network, and is available from the Stanford Large Network Dataset Collection [28]."
It is unclear which friendster dataset is used. In SNAP, http://snap.stanford.edu/data/com-Friendster.html seems to be "undirected" and has 1.8B edges, not "1.6B edges" as written in Table 1 (even after removing edges of nodes with degree larger than 10,000).
## Typos and minors:
- Inside the paper $O(100B)$ looks a bit strange, because according to [the definition](https://en.wikipedia.org/wiki/Big_O_notation#Formal_definition) the set $O(100B)$ is equal to $O(0.00001)$
- should be "more than 10K followeEs (outdegree > 10K)" not "followers".

☆

2

### Can be extended to k-cliques and k-motifs:
- To list k-cliques: https://github.com/maxdan94/kClist
- To list k-motifs: https://github.com/maxdan94/kmotif
### Typos:
- ", cf.[23],"
- "conductance problem.Notice that"
- "(CNM) [12] , Cfinder"
- "Louvaine" instead of "Louvain" in Table 2

☆

2

It's a very nice paper. There are some parts I don't fully understand yet, as I have to read more on hyperLoglog counter and webgraph framework.
### Comparison to existing methods:
Doing some experimental comparisons to [Eppstein and Wang 2004](https://papers-gamma.link/paper/35) for the closeness centrality might be interesting.
### Typos:
- $\mathscr{B}_{G}(x,r)=\{y | d(x,y) \leq r\}$ instead of $\mathscr{B}_{G}(x,r)=\{y | d(x,y) \leq t\}$
- $|\mathscr{B}_{G}(v,t)|-|\mathscr{B}_{G}(v,t-1)|$ instead of $|\mathscr{B}_{G}(v,t+1)|-|\mathscr{B}_{G}(v,t)|$. This is corrected in the other formula on centralities.
- "the the reciprocal of a"
- "can be easily computed in a cumulative fashion nothing that"
- "on the approximation the diameter"
- "its importance it by 1/2"
### Minors:
- "Nodes with empty coreachable set have centrality 1 by definition"
. By definition the coreachable set of a node is never empty, it contains at least the concerned node.

☆

1

Feel free to start an awesome discussion.
### Typos:
- "is defined as the the minimum"

## Comments: