## 5 Data Evaluation
### Datasets  
We performed our experiments on the following available datasets in public summarized in Table 2.  
* Online social networks: Flickr [22], Pokec [44], LiveJournal [44], YouTube [22], socio-Epinions1 [11], and soc-Slashdot08 [10]. Flickr, LiveJournal, and YouTube are popular photo, blog, and video sharing websites, respectively, where a user can subscribe to other user updates such as photos, blogs, and videos. Pokec is the most popular online social network in Slovakia, and has been in existence for more than ten years. These networks can be represented by directed graphs, where nodes represent users and a directed edge from node \(u\) to node \(v\) indicates that user \(u\) subscribes to user \(v\) or user \(u\) tags user \(v\) as a friend. Soc-Epinions1 [11] is a directed graph of the Epinions website in 2003, where a directed edge from node \(u\) to node \(v\) indicates that user \(u\) trusts user \(v\). Soc-Slashdot08 and Soc-Slashdot09 [10] are graphs of the technology-related news website Slashdot released in 2008 and 2009, respectively, where the edge between node \(u\) and node \(v\) means that user \(u\) has marked user \(v\) as a friend. * Web graph: Web-Google [46]. The Web-Google dataset was released in 2002 by Google as a part of a Google Programming Contest; nodes represent web pages and directed edges represent hyperlinks between them. * Signed networks: sign-Epinions, sign-Slashdot08, and sign-Slashdot09 [47]. Epinions and Slashdot networks can be represented by a signed graph, where a positive edge from user \(u\) to user \(v\) means that \(u\) trusts \(v\) in the Epinions website or \(u\) marks \(v\) as a friend on the Slashdot website. A negative edge from \(u\) to \(v\) means a distrust relationship on the Slashdot website or that \(u\) tags user \(v\) as a fo \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Graph** & **Nodes** & **Edges** & **Max-Degree** \\ \hline Flickr [22] & 1,715,255 & 15,555,041 & 27,236 \\ Pokec [44] & 1,632,803 & 22,301,964 & 14,854 \\ LiveJournal [22] & 5,189,809 & 48,688,097 & 15,017 \\ YouTube [22] & 1,138,499 & 2,990,443 & 28,754 \\ Wiki-Talk [45] & 2,394,385 & 4,659,565 & 100,029 \\ Web-Google [46] & 875,713 & 4,322,051 & 6332 \\ soc-Epinions1 [11] & 75,897 & 405,740 & 3044 \\ soc-Slashdot08 [10] & 77,360 & 469,180 & 2539 \\ soc-Slashdot09 [10] & 82,168 & 504,230 & 2552 \\ sign-Epinions [47] & 119,130 & 704,267 & 3558 \\ sign-Slashdot08 [47] & 77,350 & 416,695 & 2537 \\ sign-Slashdot09 [47] & 82,144 & 504,230 & 2552 \\ com-DBLP [48] & 317,080 & 1,049,866 & 343 \\ com-Amazon [48] & 334,863 & 925,872 & 549 \\ p2p-Gnutella08 [49] & 6301 & 20,777 & 97 \\ ca-GrQc [50] & 5241 & 14,484 & 81 \\ ca-CondMat [50] & 23,133 & 93,439 & 279 \\ ca-HepTh [50] & 9875 & 25,937 & 65 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Graph datasets used in our experiments. “edges” refers to the quantity of edges in the undirected graph generated by discarding edge labels. “max-degree” denotes the maximum quantity of edges for a node in an undirected graph. * Collaboration networks: ca-HepTh [50], ca-GrQc [50], and ca-CondMat [50]. arXiv is an online repository of electronic preprints of scientific papers in many fields, such as mathematics, physics, and computer science. The datasets ca-GR-QC, ca-HEP-TH, and ca-CondMat consist of arXiv e-prints and cover scientific collaborations between authors of papers submitted to the General Relativity and Quantum Cosmology category, the High-Energy Physics--Theory category, and the Condensed Matter category, respectively [50]. These networks can all be represented by undirected graphs. If author \(u\) co-authored a paper with author \(v\), the graph contains an undirected edge from \(u\) to \(v\). * Peer-to-peer network: p2p-Gnutella08 [49]. Gnutella is a peer-to-peer file sharing network. Nodes in the p2p-Gnutella08 dataset represent users in the Gnutella network and edges represent connections between Gnutella users. * Communication network: Wiki-Talk [45].