Introduction
-
Node-weighted centrality measures: consider only the node weights for the analysis while taking all edge weights as one.
-
Fully weighted centrality measures: consider both types of weights, edge weights and node weights for the analysis.
Unweighted centrality measures
-
Degree: Freeman’s [10] degree centrality considers that a node’s importance is proportional to its degree, number of links connected (starting/ending) to that node. Mathematically, degree centrality of a node u,Degree centrality can be normalized by dividing the above expression with \(n-1\). In a social network, degree centrality of a node represents that node’s popularity. A higher degree node has many followers/friends which shows the strength of the node. Lower degree nodes are the actors who are nearly isolated from the population of the network and are least popular.$$\begin{aligned} \text{DC}(u)=\sum \limits _{v\in V{\setminus }\{u\}} a_{uv}. \end{aligned}$$
-
Closeness: Freeman’s [10] closeness centrality considers a node’s importance to be inversely proportional to the sum of its distance to other nodes. Mathematically, closeness centrality of a node u can be represented asCloseness centrality can be normalized by multiplying the above expression with \(n-1\). The concept of closeness centrality was first given by Freeman [10] for social networks, but the concept has existed for a long time as status of a node [11]. Closeness centrality of a node in a network represents the node’s average distance, i.e., the expectation of how much time, a piece of information that started flowing from any node in the network, will take to reach that node or vice-versa. A higher closeness central node gets updated very early when some information is spreading and nodes with low closeness centrality have to wait longer for getting updated with the flowing information.$$\begin{aligned} \text{CC}(u)=\frac{1}{\sum \nolimits _{v\in V{\setminus }\{u\}} d_{uv}}. \end{aligned}$$
-
Harmonic: harmonic centrality [5, 12] considers that a node’s importance in a network is proportional to the sum of inverse of its distances from other nodes. Mathematically, harmonic centrality of a node u isFreeman’s [10] closeness centrality was not applicable on disconnected networks. Harmonic centrality is highly correlated to closeness centrality [12] and works well on disconnected and directed networks.$$\begin{aligned} {\text{HC}}(u)=\sum \limits _{v\in V{\setminus }\{u\}} \frac{1}{ d_{uv}}. \end{aligned}$$
-
Decay: this centrality works on same principle as harmonic centrality but at place of penalizing the contribution of nodes linearly, it does exponentially [3]. Mathematically, decay centrality of a node u is,where \(\delta\) lies between 0 and 1. \(\delta\) is called decay parameter.$$\begin{aligned} \text{DKC}(u)=\sum \limits _{v\in V{\setminus }\{u\}} \delta ^{d_{uv}}, \end{aligned}$$
-
Betweenness: Freeman’s [10] betweenness centrality considers that a node’s importance is proportional to the number of times that node occurs in the shortest paths between all possible pairs of nodes in a network. Mathematically, betweenness centrality of a node u,where \(\sigma _{\text{st}}\) is the total number of shortest paths from node s to node t and \(\sigma _{\text{st}}(u)\) is the total number of shortest paths from node s to node t passing through node u. Betweenness centrality can be normalized by dividing with \(\frac{(n-1)(n-2)}{2}\). The concept of betweenness centrality was first proposed by Anthonisse [13] and Freeman [14] independently. Betweenness centrality of a node in a network represents the node’s brokerage power, i.e., control over the flow passing through the network with the assumption that information is flowing through shortest paths. A higher betweenness central node controls a major fraction of flow passing through the network while a low betweenness central node has nearly no such control.$$\begin{aligned} \text{BC}(u)=\sum \limits _{s,t,u\in V: |\{s,t,v\}|=3}\frac{\sigma _{\text{st}}(u)}{\sigma _{\text{st}}}, \end{aligned}$$
-
Eigenvector: Bonacich’s [15] eigenvector centrality considers that a node’s importance in a network is proportional to the sum of the importance of neighboring nodes in that network. Mathematically, eigenvector centrality of a node u can be written as,Eigenvector centrality of a node in a network represents the power of a node’s neighbors in the network. A node with high eigenvector centrality indicates the direct connection of this node to important nodes in the network and vice-versa.$$\begin{aligned} \text{EC}(u)=\sum \limits _{v\in V{\setminus }\{u\}}( a_{uv} \cdot \text{EC}(v)). \end{aligned}$$
Toy examples
Node-weighted centrality
-
Node-weighted degree centrality: in [6], weights on nodes are considered and the definition of degree centrality is modified to accommodate the node weights. Abbasi and Hossain [6] considered centrality scores as weights on the nodes. Following it, node-weighted centrality of a node u is calculated as:This measure assigns higher importance to those nodes which are in the immediate neighborhood of highly weighted nodes. Next two measures extend the consideration to all the nodes to compute the eminence of a node.$$\begin{aligned} \frac{\sum \nolimits _{v\in V {\setminus } \{u\}} (f (W_v)\cdot a_{u,v})}{ \sum \limits _{x\in V} f(W_x) }. \end{aligned}$$
-
Node-weighted closeness/harmonic centrality: to target the wider applicability, we define node-weighted harmonic centrality (which also can be used in the case of closeness centrality computation as both are highly correlated). Node-weighted harmonic centrality of a node u in a network is defined as:This measure depends on two factors: weight of the node u under consideration and the effective weights of other nodes corresponding to their distances from node u. It assigns a higher value to the nodes that are of high weights and closer to the nodes with high weights. We refer this measure as harmonically attenuated node-weighted centrality measure.$$\begin{aligned} \frac{f(W_u)+\sum \nolimits _{v\in V{\setminus }\{u\}}\frac{f(W_v)}{d_{u,v}+1}}{\sum \nolimits _{x\in V}f(W_x)}. \end{aligned}$$
-
Node weighed decay: weighted decay of a node u in a network as defined aswhere \(\delta\) lies between 0 and 1. Here also the computation of importance depends on the same two factors as in NWCC. But, the contribution of weights of other nodes decays exponentially with distance. Weighted decay assigns a higher value to the nodes that are of high weights and very close to the nodes with high weights. We refer this measure as exponentially attenuated node weighted centrality measure.$$\begin{aligned} \frac{f(W_u)+\sum \nolimits _{v\in V{\setminus }\{u\}} (\delta ^{d_{u,v}}\cdot f(W_v))}{\sum \nolimits _{x\in V} f(W_x)}, \end{aligned}$$
-
Node-weighted betweenness centrality: in [16], a factor denoting the importance of communication between two pairs is multiplied in the core formula while computing the betweenness centrality. The node-weighted betweenness centrality of a node u was defined aswhere \(f(W_x , W_y)\) can be assumed to map the weights given on node x and y to a real value denoting the importance of flow happening between x and y.$$\begin{aligned} \frac{\sum \nolimits _{s,t,u\in V: |\{s,t,v\}|=3}f(W_s,W_t)\cdot \frac{\sigma _{\text{st}}(u)}{\sigma _{\text{st}}}}{\sum \nolimits _{x,y,u\in V: |\{x,y,v\}|=3}f(W_x,W_y)}, \end{aligned}$$
Related work
The service coverage problem
Formulation
-
Harmonically attenuated-betweenness centrality (HABC): this measure is based on the harmonic attenuation of importance with respect to the distance. The harmonically attenuated-betweenness centrality of a node u is defined as,where BC(u) is the unweighted betweenness centrality of node u. This hybrid measure assigns a value that is calculated based on an averaging function of distances and betweenness centrality. This measure assigns a higher value to the nodes that are of high betweenness and closer to other high betweenness central nodes. This measure solves the SCP problem in flow networks where the response-efficiency decays harmonically.$$\begin{aligned} \text{HABC}(u)=\frac{\text{BC}(u)+\sum _{v\in V{\setminus }\{u\}} \frac{\text{BC}(v)}{d_{u,v}+1}}{\sum _{w\in V} \text{BC}(w)}, \end{aligned}$$
-
Exponentially attenuated-betweenness centrality (EABC): this measure is based on an exponential attenuation in the power of distance. The exponentially attenuated-betweenness centrality of a node u is defined as,where BC(u) is the betweenness centrality of node i. \(\alpha\) is the attenuation factor that is used in the exponential function to the power of distance. It is used to sharply punish the service time. This hybrid measure assigns a value that is calculated based on betweenness centrality of nodes and an exponential function in the power of distances. This measure assigns a higher value to the nodes that are of high betweenness and very close to other high betweenness central nodes. This centrality measure is a sharp attenuation variant of harmonically attenuated-degree centrality. This measure solves the service coverage problem when the service is required on a very urgent basis.$$\begin{aligned} \text{EABC}(u)=\frac{\text{BC}(u)+\sum _{v\in V{\setminus }\{u\}} \alpha ^{d_{u,v}}\cdot \text{BC}(v)}{\sum _{w\in V} \text{BC}(w)}, \end{aligned}$$
Experimental results for service coverage problem
Instance name | n | m | Avg. deg. | Density | \(\hat{C}\) | Assortativity (D) | Max clique | Network type |
---|---|---|---|---|---|---|---|---|
Chicago Road [36] | 1467 | 1298 | 1.7696 | 0.0012 | 0.0001 | \(-\) 0.5049 | 2 | Transport network |
Chilean Power Grid [38] | 347 | 444 | 2.5591 | 0.0074 | 0.0865 | \(-\) 0.0773 | 4 | Energy network |
Euroroad [36] | 1174 | 1417 | 2.414 | 0.0021 | 0.0167 | 0.1267 | 3 | Transport network |
London Metro [34] | 266 | 308 | 2.3158 | 0.0087 | 0.0363 | 0.1531 | 3 | Transport network |
Madrid Metro [34] | 209 | 240 | 2.2967 | 0.011 | 0.0056 | 0.1776 | 3 | Transport network |
Mexico Metro [34] | 147 | 164 | 2.2313 | 0.0153 | 0.0034 | \(-\) 0.1105 | 3 | Transport network |
Minnesota Road [31] | 2642 | 3303 | 2.5004 | 0.0009 | 0.016 | \(-\) 0.1848 | 3 | Transport network |
Moscow Metro [34] | 134 | 156 | 2.3284 | 0.0175 | 0.0174 | 0.4492 | 3 | Transport network |
New York Metro [34] | 433 | 475 | 2.194 | 0.0051 | 0.0173 | \(-\) 0.0297 | 3 | Transport network |
Oldenburg Road [32] | 6105 | 7029 | 2.3027 | 0.0004 | 0.0108 | 0.0554 | 3 | Transport network |
Openflights [34] | 2939 | 15677 | 10.6683 | 0.0036 | 0.4526 | 0.0509 | 22 | Transport network |
Osaka Metro [34] | 108 | 123 | 2.2778 | 0.0213 | 0.0001 | 0.1965 | 2 | Transport network |
p2p-Gnutella08 [37] | 6301 | 20777 | 6.5948 | 0.001 | 0.0109 | 0.0356 | 5 | Internet peer-to-peer network |
Paris Metro [34] | 299 | 356 | 2.3813 | 0.008 | 0.0204 | \(-\) 0.0297 | 3 | Transport network |
as20000102 [37] | 6474 | 13895 | 4.2926 | 0.0007 | 0.2522 | \(-\) 0.1704 | 10 | Autonomous systems graph |
Seoul Metro [34] | 392 | 437 | 2.2296 | 0.0057 | 0.006 | 0.0313 | 3 | Transport network |
Shanghai Metro [34] | 148 | 158 | 2.1351 | 0.0145 | 0.0029 | \(-\) 0.0318 | 3 | Transport network |
Tokyo Metro [34] | 217 | 262 | 2.4147 | 0.0112 | 0.0237 | 0.1983 | 3 | Transport network |
US Air [35] | 332 | 2126 | 12.8072 | 0.0387 | 0.6252 | \(-\) 0.2079 | 22 | Transport network |
US Power Grid [39] | 4941 | 6594 | 2.6691 | 0.0005 | 0.0801 | 0.0035 | 6 | Energy network |
NRPG data [33] | 246 | 373 | 3.0325 | 0.0124 | 0.1071 | \(-\) 0.0932 | 3 | Energy network |
Instance name | BC | DC | CC | EC | HABC | EABC (\(\alpha =0.5\)) | EABC (\(\alpha =0.75\)) |
---|---|---|---|---|---|---|---|
Chicago Road | 0.49 | 0.49 | 0.49 | 0.49 | 0.49 | 0.49 | 0.49 |
Chilean Power Grid | 0.29 | 0.33 | 0.29 | 0.33 | 0.29 | 0.29 | 0.29 |
Euroroad | 0.88 | 0.88 | 0.89 | 1.05 | 0.88 | 0.88 | 0.88 |
London Metro | 0.83 | 0.83 | 0.80 | 0.83 | 0.80 | 0.80 | 0.80 |
Madrid Metro | 0.46 | 0.46 | 0.44 | 0.66 | 0.46 | 0.46 | 0.42 |
Mexico Metro | 0.50 | 0.50 | 0.54 | 0.50 | 0.50 | 0.50 | 0.54 |
Minnesota Road | 2.29 | 3.21 | 2.15 | 3.11 | 3.29 | 2.29 | 3.45 |
Moscow Metro | 0.40 | 0.40 | 0.37 | 0.39 | 0.39 | 0.39 | 0.37 |
New York Metro | 1.11 | 1.3 | 1.12 | 1.3 | 1.11 | 1.11 | 1.11 |
Oldenburg Road | 1.66 | 1.66 | 1.68 | 2.64 | 1.66 | 1.66 | 1.66 |
Openflights | 0.16 | 0.16 | 0.16 | 0.16 | 0.16 | 0.16 | 0.16 |
Osaka Metro | 0.48 | 0.48 | 0.44 | 0.48 | 0.48 | 0.48 | 0.42 |
p2p-Gnutella08 | 0.29 | 0.27 | 0.27 | 0.27 | 0.27 | 0.27 | 0.27 |
Paris Metro | 0.55 | 0.55 | 0.55 | 0.56 | 0.51 | 0.51 | 0.51 |
as20000102 | 0.12 | 0.12 | 0.12 | 0.12 | 0.12 | 0.12 | 0.12 |
Seoul Metro | 1.06 | 1.25 | 1.06 | 1.23 | 1.02 | 1.02 | 1.02 |
Shanghai Metro | 0.53 | 0.53 | 0.64 | 0.53 | 0.64 | 0.53 | 0.64 |
Tokyo Metro | 0.57 | 0.57 | 0.57 | 0.57 | 0.57 | 0.57 | 0.49 |
US Air | 0.10 | 0.10 | 0.10 | 0.10 | 0.10 | 0.10 | 0.10 |
US Power Grid | 0.92 | 1.34 | 0.83 | 2.12 | 0.83 | 0.83 | 0.83 |
NRPG | 0.30 | 0.45 | 0.30 | 0.37 | 0.30 | 0.30 | 0.30 |
Instance name | HABC | EABC (\(\alpha =0.5)\) | EABC (\(\alpha =0.75)\) | BC | CC | DC | EC | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
R1 | R2 | R3 | R1 | R2 | R3 | R1 | R2 | R3 | R1 | R2 | R3 | R1 | R2 | R3 | R1 | R2 | R3 | R1 | R2 | R3 | |
Chicago Road | 1156 | 1157 | 1147 | 1156 | 1157 | 1147 | 1156 | 1157 | 1147 | 1156 | 1157 | 1147 | 1156 | 1157 | 1147 | 552 | 922 | 10 | 1156 | 1147 | 1150 |
Chilean Power Grid | 178 | 105 | 147 | 178 | 105 | 147 | 178 | 105 | 147 | 178 | 105 | 108 | 178 | 105 | 147 | 108 | 6 | 178 | 108 | 264 | 29 |
Euroroad | 402 | 284 | 277 | 402 | 284 | 277 | 402 | 284 | 277 | 402 | 284 | 277 | 401 | 402 | 403 | 284 | 7 | 39 | 7 | 43 | 454 |
London Metro | 115 | 29 | 12 | 115 | 29 | 12 | 115 | 29 | 12 | 12 | 115 | 180 | 115 | 29 | 214 | 12 | 164 | 305 | 214 | 115 | 219 |
Madrid Metro | 80 | 162 | 146 | 80 | 162 | 146 | 162 | 80 | 146 | 80 | 146 | 162 | 162 | 80 | 235 | 80 | 15 | 9 | 15 | 54 | 40 |
Mexico Metro | 26 | 70 | 23 | 26 | 70 | 78 | 70 | 26 | 54 | 26 | 70 | 25 | 70 | 26 | 23 | 26 | 127 | 61 | 26 | 70 | 23 |
Minnesota Road | 300 | 328 | 280 | 1821 | 2069 | 300 | 280 | 328 | 300 | 1821 | 2069 | 2063 | 1356 | 1820 | 1109 | 2418 | 35 | 32 | 1927 | 1930 | 1987 |
Moscow Metro | 59 | 71 | 25 | 59 | 71 | 25 | 71 | 59 | 73 | 25 | 74 | 59 | 73 | 71 | 25 | 24 | 59 | 21 | 59 | 25 | 73 |
New York Metro | 424 | 191 | 410 | 424 | 191 | 410 | 424 | 191 | 410 | 424 | 191 | 148 | 84 | 424 | 410 | 273 | 228 | 410 | 273 | 228 | 188 |
Oldenburg Road | 831 | 714 | 731 | 831 | 714 | 711 | 831 | 714 | 803 | 831 | 714 | 593 | 714 | 731 | 712 | 831 | 1657 | 1571 | 1677 | 1683 | 1691 |
Openflights | 53 | 65 | 57 | 53 | 57 | 65 | 53 | 57 | 65 | 53 | 65 | 1576 | 53 | 65 | 57 | 53 | 65 | 59 | 53 | 59 | 65 |
Osaka Metro | 25 | 70 | 95 | 25 | 70 | 95 | 70 | 95 | 25 | 25 | 99 | 70 | 95 | 70 | 25 | 25 | 54 | 42 | 25 | 81 | 54 |
p2p-Gnutella08 | 123 | 367 | 127 | 123 | 367 | 127 | 123 | 127 | 367 | 5831 | 1317 | 424 | 123 | 127 | 1317 | 123 | 127 | 367 | 367 | 123 | 145 |
Paris Metro | 150 | 57 | 235 | 150 | 57 | 235 | 150 | 57 | 235 | 57 | 150 | 106 | 57 | 150 | 235 | 57 | 177 | 246 | 186 | 150 | 235 |
as20000102 | 2 | 10 | 7 | 2 | 10 | 7 | 2 | 10 | 7 | 2 | 7 | 10 | 2 | 10 | 7 | 2 | 10 | 7 | 2 | 10 | 7 |
Seoul Metro | 220 | 480 | 357 | 220 | 444 | 391 | 220 | 480 | 357 | 220 | 444 | 391 | 220 | 480 | 357 | 254 | 444 | 391 | 103 | 254 | 125 |
Shanghai Metro | 136 | 16 | 113 | 136 | 16 | 213 | 136 | 113 | 16 | 16 | 136 | 65 | 136 | 113 | 97 | 16 | 136 | 220 | 16 | 137 | 138 |
Tokyo Metro | 150 | 85 | 53 | 150 | 85 | 53 | 85 | 150 | 60 | 150 | 53 | 85 | 150 | 60 | 85 | 150 | 53 | 120 | 150 | 120 | 36 |
US Air | 118 | 261 | 201 | 118 | 201 | 47 | 118 | 201 | 47 | 118 | 8 | 261 | 118 | 261 | 67 | 118 | 261 | 255 | 118 | 261 | 255 |
US Power Grid | 1378 | 1365 | 2685 | 1378 | 1365 | 2685 | 1378 | 1365 | 1678 | 651 | 559 | 1365 | 1378 | 1678 | 2944 | 2847 | 602 | 932 | 4422 | 4436 | 4419 |
NRPG data | 233 | 235 | 238 | 233 | 235 | 238 | 233 | 235 | 238 | 70 | 235 | 213 | 233 | 238 | 70 | 194 | 65 | 56 | 239 | 213 | 215 |
Instance name | HABC | EABC (\(\alpha =0.5)\) | EABC (\(\alpha =0.75)\) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
BC | CC | DC | EC | BC | CC | DC | EC | BC | CC | DC | EC | |
Chicago Road | 0.2087 | 0.3688 | 0.2393 | 0.2027 | 0.2040 | 0.3437 | 0.2351 | 0.2024 | 0.2035 | 0.3241 | 0.1985 | 0.1515 |
Chilean Power Grid | 0.0691 | \(-\) 0.0620 | 0.0132 | 0.0057 | 0.0224 | 0.0274 | 0.0506 | 0.0163 | 0.0929 | 0.0867 | \(-\) 0.0200 | 0.0850 |
Euroroad | 0.7707 | 0.0144 | 0.2019 | \(-\) 0.0010 | 0.7985 | 0.0190 | 0.1675 | \(-\) 0.0174 | 0.7656 | 0.0214 | 0.1834 | \(-\) 0.0227 |
London Metro | 0.1625 | 0.1450 | 0.0296 | 0.0312 | \(-\) 0.0291 | 0.0323 | 0.0917 | 0.0636 | 0.0432 | 0.1496 | \(-\)0.0837 | 0.0324 |
Madrid Metro | 0.0540 | 0.1561 | \(-\) 0.0912 | 0.0149 | 0.0284 | 0.0891 | \(-\) 0.0949 | 0.1213 | 0.0109 | 0.0814 | \(-\) 0.1316 | 0.0049 |
Mexico Metro | \(-\)0.0598 | 0.2043 | 0.0428 | 0.1145 | 0.1267 | \(-\)0.0479 | 0.0516 | 0.1401 | \(-\) 0.0037 | 0.2043 | \(-\)0.0716 | 0.1522 |
Minnesota Road | \(-\)0.0068 | \(-\)0.0358 | \(-\) 0.0777 | \(-\) 0.1648 | 0.0286 | \(-\) 0.0221 | 0.0075 | \(-\) 0.0393 | 0.0015 | \(-\) 0.0552 | 0.0345 | \(-\) 0.1444 |
Moscow Metro | 0.0824 | 0.0474 | 0.1245 | 0.0570 | \(-\) 0.1814 | \(-\) 0.1215 | \(-\) 0.2326 | 0.0627 | 0.1012 | 0.0468 | 0.0331 | \(-\) 0.1045 |
New York Metro | 0.0386 | 0.0865 | \(-\) 0.0061 | 0.0760 | 0.0599 | 0.0394 | \(-\) 0.0382 | \(-\) 0.0222 | 0.0083 | \(-\) 0.0139 | \(-\) 0.0651 | \(-\) 0.0156 |
Oldenburg Road | 0.0098 | 0.1332 | 0.0094 | \(-\) 0.0222 | 0.0075 | 0.0593 | 0.0202 | 0.0169 | 0.0113 | 0.0991 | 0.0039 | \(-\) 0.0083 |
Openflights | 0.0018 | 0.1090 | 0.0263 | 0.0799 | 0.0055 | 0.1417 | 0.0318 | 0.0898 | 0.0032 | 0.1305 | 0.0200 | 0.0618 |
Osaka Metro | 0.0110 | 0.1728 | 0.0262 | 0.1440 | 0.0482 | 0.1662 | 0.0402 | 0.1398 | 0.0795 | 0.1031 | \(-\) 0.0713 | 0.0656 |
p2p-Gnutella08 | 0.0537 | 0.0760 | 0.0880 | 0.0491 | 0.0636 | 0.0634 | 0.0775 | 0.0485 | 0.0660 | 0.0529 | 0.0754 | 0.0561 |
as20000102 | 0.1327 | 0.5878 | 0.1837 | 0.4513 | 0.1408 | 0.5881 | 0.1810 | 0.4423 | 0.1309 | 0.6273 | 0.1912 | 0.4392 |
Seoul Metro | 0.0520 | \(-\) 0.0055 | \(-\) 0.0048 | \(-\) 0.0389 | 0.0257 | 0.0143 | 0.0480 | 0.0775 | \(-\) 0.0427 | 0.0109 | \(-\) 0.0643 | 0.0136 |
Shanghai Metro | 0.1104 | \(-\) 0.0165 | 0.1168 | 0.0977 | 0.0721 | 0.1124 | 0.0326 | 0.1617 | 0.0014 | 0.0922 | 0.1809 | 0.0610 |
US Air | 0.0855 | 0.1707 | 0.0522 | 0.0608 | 0.1171 | 0.2246 | 0.0059 | 0.0674 | 0.0503 | 0.2372 | 0.0243 | 0.1065 |
US Power Grid | 0.0450 | 0.0831 | 0.0830 | 0.0437 | 0.0350 | 0.0279 | 0.0345 | 0.0038 | 0.0436 | 0.0598 | 0.0622 | 0.0436 |
Paris Metro | \(-\) 0.1077 | 0.0421 | \(-\)0.0625 | 0.1169 | 0.0302 | 0.0846 | \(-\) 0.0271 | 0.0351 | 0.0175 | 0.1305 | \(-\) 0.0914 | 0.0309 |
Tokyo Metro | 0.1693 | 0.0920 | 0.0064 | 0.0460 | 0.0555 | 0.0883 | 0.0958 | 0.0511 | 0.0646 | 0.1071 | \(-\) 0.0794 | 0.1039 |
NRPG data | 0.0118 | 0.1334 | \(-\) 0.0693 | 0.0934 | 0.0445 | 0.0975 | \(-\) 0.1389 | 0.1395 | \(-\) 0.0867 | 0.1659 | \(-\) 0.1322 | 0.0936 |
Average correlation | 0.0902 | 0.1192 | 0.0444 | 0.0694 | 0.0811 | 0.0966 | 0.0305 | 0.0858 | 0.0744 | 0.1268 | 0.0094 | 0.0574 |
Standard deviation | 0.1729 | 0.1441 | 0.0907 | 0.1152 | 0.1802 | 0.1485 | 0.1043 | 0.1042 | 0.1701 | 0.1432 | 0.1069 | 0.1139 |
Instance name | HABC | EABC (\(\alpha =0.5)\) | EABC (\(\alpha =0.75)\) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
BC | CC | DC | EC | BC | CC | DC | EC | BC | CC | DC | EC | |
Chicago Road | 0.2402 | 0.2919 | 0.2531 | 0.1375 | 0.2493 | 0.2762 | 0.2601 | 0.1197 | 0.2375 | 0.2669 | 0.2267 | 0.1024 |
Chilean Power Grid | 0.0461 | \(-\) 0.0379 | 0.0089 | 0.0045 | 0.0149 | 0.0197 | 0.0318 | 0.0119 | 0.0621 | 0.0651 | \(-\) 0.0153 | 0.0556 |
Euroroad | 0.7126 | 0.0099 | 0.1404 | \(-\) 0.0004 | 0.7461 | 0.0127 | 0.1168 | \(-\) 0.0115 | 0.7025 | 0.0147 | 0.1278 | \(-\) 0.0149 |
London Metro | 0.1074 | 0.0972 | 0.0173 | 0.0220 | \(-\) 0.0200 | 0.0241 | 0.0617 | 0.0445 | 0.0286 | 0.1022 | \(-\) 0.0568 | 0.0241 |
Madrid Metro | 0.0334 | 0.1058 | \(-\)0.0609 | 0.0098 | 0.0215 | 0.0595 | \(-\) 0.0647 | 0.0846 | 0.0097 | 0.0558 | \(-\) 0.0885 | 0.0077 |
Mexico Metro | \(-\) 0.0445 | 0.1386 | 0.0264 | 0.0724 | 0.0860 | \(-\) 0.0351 | 0.0338 | 0.1026 | \(-\)0.0040 | 0.1376 | \(-\) 0.0566 | 0.1047 |
Minnesota Road | \(-\) 0.0047 | \(-\) 0.0216 | \(-\) 0.0432 | \(-\) 0.1205 | 0.0190 | \(-\) 0.0143 | 0.0052 | \(-\) 0.0264 | 0.0012 | \(-\) 0.0370 | 0.0232 | \(-\) 0.0999 |
Moscow Metro | 0.0553 | 0.0315 | 0.0809 | 0.0376 | \(-\) 0.1274 | \(-\) 0.0807 | \(-\) 0.1592 | 0.0439 | 0.0690 | 0.0349 | 0.0250 | \(-\) 0.0722 |
New York Metro | 0.0259 | 0.0582 | \(-\) 0.0040 | 0.0501 | 0.0399 | 0.0265 | \(-\)0.0254 | \(-\) 0.0143 | 0.0067 | \(-\) 0.0095 | \(-\) 0.0429 | \(-\) 0.0094 |
Oldenburg Road | 0.0066 | 0.0905 | 0.0067 | \(-\) 0.0146 | 0.0051 | 0.0401 | 0.0136 | 0.0118 | 0.0074 | 0.0671 | 0.0029 | \(-\)0.0056 |
Openflights | 0.0053 | 0.0797 | 0.0217 | 0.0571 | 0.0077 | 0.1029 | 0.0249 | 0.0645 | 0.0061 | 0.0936 | 0.0184 | 0.0443 |
Osaka Metro | 0.0097 | 0.1222 | 0.0194 | 0.1038 | 0.0301 | 0.1177 | 0.0280 | 0.1000 | 0.0568 | 0.0723 | \(-\) 0.0519 | 0.0561 |
p2p-Gnutella08 | 0.0364 | 0.0514 | 0.0595 | 0.0329 | 0.0433 | 0.0427 | 0.0524 | 0.0326 | 0.0447 | 0.0360 | 0.0513 | 0.0379 |
as20000102 | 0.0909 | 0.4913 | 0.1318 | 0.3756 | 0.0963 | 0.4917 | 0.1303 | 0.3696 | 0.0900 | 0.5191 | 0.1367 | 0.3672 |
Seoul Metro | 0.0349 | \(-\) 0.0052 | \(-\) 0.0031 | \(-\) 0.0280 | 0.0165 | 0.0090 | 0.0305 | 0.0527 | \(-\) 0.0281 | 0.0056 | \(-\) 0.0439 | 0.0112 |
Shanghai Metro | 0.0761 | \(-\) 0.0097 | 0.0798 | 0.0689 | 0.0506 | 0.0735 | 0.0182 | 0.1158 | 0.0029 | 0.0671 | 0.1129 | 0.0421 |
US Air | 0.0568 | 0.1184 | 0.0345 | 0.0401 | 0.0782 | 0.1584 | 0.0051 | 0.0473 | 0.0339 | 0.1685 | 0.0186 | 0.0717 |
US Power Grid | 0.0304 | 0.0559 | 0.0558 | 0.0294 | 0.0234 | 0.0186 | 0.0229 | 0.0025 | 0.0292 | 0.0406 | 0.0418 | 0.0289 |
Paris Metro | \(-\) 0.0721 | 0.0269 | \(-\) 0.0417 | 0.0795 | 0.0186 | 0.0589 | \(-\) 0.0180 | 0.0217 | 0.0119 | 0.0928 | \(-\) 0.0620 | 0.0184 |
Tokyo Metro | 0.1150 | 0.0610 | 0.0063 | 0.0311 | 0.0384 | 0.0608 | 0.0626 | 0.0315 | 0.0445 | 0.0742 | \(-\) 0.0559 | 0.0707 |
NRPG data | 0.0069 | 0.0888 | \(-\) 0.0416 | 0.0598 | 0.0283 | 0.0660 | \(-\) 0.0889 | 0.0972 | \(-\) 0.0596 | 0.1109 | \(-\) 0.0914 | 0.0625 |
Average correlation | 0.0747 | 0.0878 | 0.0356 | 0.0499 | 0.0698 | 0.0728 | 0.0258 | 0.0620 | 0.0644 | 0.0942 | 0.0105 | 0.0430 |
Standard deviation | 0.1594 | 0.1167 | 0.0729 | 0.0911 | 0.1684 | 0.1205 | 0.0833 | 0.0830 | 0.1572 | 0.1172 | 0.0835 | 0.0895 |
Instance name | HABC | EABC (\(\alpha =0.5)\) | EABC (\(\alpha =0.75)\) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
BC | CC | DC | EC | BC | CC | DC | EC | BC | CC | DC | EC | |
Chicago Road | 0.6487 | 0.8122 | 0.6106 | 0.8187 | 0.6639 | 0.7809 | 0.6286 | 0.7873 | 0.6308 | 0.8073 | 0.5992 | 0.816 |
Chilean Power Grid | 0.7007 | 0.9529 | 0.6461 | 0.7418 | 0.7105 | 0.9212 | 0.6553 | 0.7361 | 0.6912 | 0.966 | 0.6398 | 0.7416 |
Euroroad | 0.9986 | 0.5866 | 0.6477 | 0.4884 | 0.9992 | 0.5869 | 0.648 | 0.4888 | 0.9983 | 0.5863 | 0.6477 | 0.4882 |
London Metro | 0.6801 | 0.9379 | 0.6831 | 0.8843 | 0.7217 | 0.8795 | 0.7013 | 0.8351 | 0.6582 | 0.9546 | 0.6729 | 0.8954 |
Madrid Metro | 0.7071 | 0.9205 | 0.6645 | 0.7385 | 0.749 | 0.8651 | 0.6862 | 0.6978 | 0.6809 | 0.9407 | 0.6542 | 0.7437 |
Mexico Metro | 0.7546 | 0.9159 | 0.6332 | 0.9014 | 0.7898 | 0.8676 | 0.6409 | 0.858 | 0.7289 | 0.9326 | 0.618 | 0.9006 |
Minnesota Road | 0.2845 | 0.1173 | 0.3375 | 0.0239 | 0.6407 | 0.2839 | 0.3661 | 0.1631 | 0.3023 | 0.1223 | 0.3434 | 0.0615 |
Moscow Metro | 0.7809 | 0.9413 | 0.7758 | 0.9056 | 0.7967 | 0.9193 | 0.7825 | 0.8875 | 0.7615 | 0.9596 | 0.7769 | 0.9083 |
New York Metro | 0.704 | 0.9081 | 0.6248 | 0.7317 | 0.7949 | 0.7963 | 0.6488 | 0.658 | 0.7004 | 0.9022 | 0.6253 | 0.7257 |
Oldenburg Road | 0.493 | 0.8842 | 0.1815 | 0.1423 | 0.7121 | 0.6117 | 0.2158 | 0.1234 | 0.5207 | 0.8129 | 0.1877 | 0.129 |
Openflights | 0.5825 | 0.9675 | 0.7762 | 0.8194 | 0.5798 | 0.9674 | 0.7753 | 0.8207 | 0.5765 | 0.9632 | 0.7704 | 0.8194 |
Osaka Metro | 0.7505 | 0.9264 | 0.6979 | 0.869 | 0.7758 | 0.8949 | 0.7085 | 0.8427 | 0.7134 | 0.958 | 0.6749 | 0.8659 |
p2p-Gnutella08 | 0.4044 | 0.926 | 0.5036 | 0.8427 | 0.3999 | 0.9203 | 0.4997 | 0.8474 | 0.4049 | 0.9291 | 0.5057 | 0.8394 |
as20000102 | 0.3204 | 0.9779 | 0.4107 | 0.8947 | 0.3181 | 0.9792 | 0.4085 | 0.8932 | 0.3245 | 0.9823 | 0.4143 | 0.8864 |
Seoul Metro | 0.6927 | 0.9099 | 0.6274 | 0.709 | 0.7945 | 0.794 | 0.6263 | 0.641 | 0.6883 | 0.9047 | 0.6269 | 0.7098 |
Shanghai Metro | 0.7429 | 0.8944 | 0.6196 | 0.7672 | 0.7999 | 0.8264 | 0.6534 | 0.7504 | 0.7165 | 0.92 | 0.6016 | 0.7629 |
US Air | 0.8097 | 0.9562 | 0.8614 | 0.8836 | 0.8056 | 0.9541 | 0.8574 | 0.8823 | 0.8026 | 0.951 | 0.8538 | 0.8786 |
US Power Grid | 0.5087 | 0.8876 | 0.2427 | 0.1926 | 0.5869 | 0.7553 | 0.2679 | 0.1789 | 0.5025 | 0.8659 | 0.2449 | 0.1949 |
Paris Metro | 0.7242 | 0.9392 | 0.6342 | 0.9106 | 0.7554 | 0.8876 | 0.6523 | 0.8702 | 0.7059 | 0.955 | 0.6258 | 0.9207 |
Tokyo Metro | 0.7012 | 0.932 | 0.6779 | 0.8424 | 0.7305 | 0.8956 | 0.69 | 0.8181 | 0.6758 | 0.9439 | 0.6631 | 0.843 |
NRPG data | 0.8047 | 0.9426 | 0.6834 | 0.7305 | 0.8181 | 0.917 | 0.694 | 0.7396 | 0.7833 | 0.9572 | 0.6749 | 0.7213 |
Average correlation | 0.6569 | 0.8684 | 0.5971 | 0.7066 | 0.7116 | 0.8240 | 0.6098 | 0.6914 | 0.6461 | 0.8721 | 0.5915 | 0.7073 |
Standard deviation | 0.1715 | 0.1903 | 0.1716 | 0.2655 | 0.1480 | 0.1613 | 0.1659 | 0.2452 | 0.1629 | 0.1929 | 0.1671 | 0.2621 |
Spread maximization in complex contagion
Formulation
-
Harmonically attenuated degree centrality (HADC): in this measure, we attenuate the node weights harmonically with respect to distance. Formally, for a node u, the HADC(u) can be expressed aswhere DC(v) is the degree centrality of node v, m is the number of links in the graph.$$\begin{aligned} \text{HADC}(u)=\frac{\text{DC}(u) +\sum _{v\in V{\setminus }\{u\}} \frac{\text{DC}(v)}{d_{u,v}+1}}{2m}, \end{aligned}$$
-
Exponentially attenuated degree centrality (EADC): in this measure, we attenuate the node weights exponentially with respect to distance. Formally, for a node u, the EADC(u) can be expressed as,where \(\alpha\) is a parameter that lies between 0 and 1, m is the number of links in the graph, DC(v) is the degree centrality of node v.$$\begin{aligned} \text{EADC}(u)=\frac{\text{DC}(u)+\sum _{v\in V{\setminus }\{u\}} \alpha ^{d_{u,v}}\cdot \text{DC}(v)}{2m}, \end{aligned}$$
Experimental results for spread maximization problem
Instance name | n | m | Avg. deg. | Density | \(\hat{C}\) | Assortativity (D) | Max clique |
---|---|---|---|---|---|---|---|
soc-gplus [31] | 23,628 | 39,242 | 3.3217 | 0.0001 | 0.0037 | \(-\) 0.387 | 7 |
Twitter Lists [36] | 23,370 | 33,101 | 2.8328 | 0.0001 | 0.0215 | \(-\) 0.4741 | 7 |
soc-hamsterer [31] | 2426 | 16,630 | 13.7098 | 0.0057 | 0.2314 | 0.0474 | 25 |
soc-pages-government [31] | 7057 | 89,455 | 25.3521 | 0.0036 | 0.2238 | 0.0294 | 28 |
soc-pages-politician [31] | 5908 | 41,729 | 14.1263 | 0.0024 | 0.3011 | 0.0184 | 21 |
soc-pages-shows [31] | 3892 | 17,262 | 8.8705 | 0.0023 | 0.5906 | 0.5605 | 57 |
soc-wiki-elec [31] | 7118 | 107,071 | 30.0846 | 0.0042 | 0.1255 | \(-\) 0.0514 | 17 |
soc-advogato [31] | 6551 | 51,332 | 15.6715 | 0.0024 | 0.0925 | \(-\) 0.0526 | 19 |
soc-pages-public-figure [31] | 11,565 | 67,114 | 11.6064 | 0.001 | 0.1666 | 0.2024 | 21 |
soc-anybeat [31] | 12,645 | 67,053 | 10.6055 | 0.0008 | 0.0217 | \(-\) 0.1219 | 25 |
soc-pages-sport [31] | 13,866 | 86,858 | 12.5282 | 0.0009 | 0.1292 | \(-\) 0.0268 | 29 |
soc-epinions [31] | 26,588 | 100,120 | 7.5312 | 0.0003 | 0.0892 | 0.0572 | 16 |
soc-pages-media [31] | 27,917 | 206,259 | 14.7766 | 0.0005 | 0.114 | 0.0221 | 31 |
soc-pages-company [31] | 14,113 | 52,310 | 7.413 | 0.0005 | 0.1532 | 0.0135 | 21 |
soc-gamesec-RO [31] | 41,773 | 125,826 | 6.0243 | 0.0001 | 0.0753 | 0.114 | 7 |
Instance name | BC | CC | DC | EC | HADC | EADC (\(\alpha =0.25\)) | EADC (\(\alpha =0.5\)) | EADC (\(\alpha =0.75\)) |
---|---|---|---|---|---|---|---|---|
soc-gplus | 1,4951 | 14,951 | 14,951 | 14,951 | 14,951 | 14,951 | 14,951 | 14,951 |
Twitter Lists | 484 | 1180 | 553 | 539 | 1180 | 1180 | 1180 | 1180 |
soc-hamsterer | 1879 | 1879 | 1879 | 1879 | 1879 | 1879 | 1879 | 1879 |
soc-pages-government | 4316 | 4316 | 4316 | 3695 | 4316 | 4316 | 4316 | 4316 |
soc-pages-politician | 2185 | 2185 | 946 | 674 | 2185 | 2185 | 2185 | 2185 |
soc-pages-shows | 1283 | 1283 | 1242 | 210 | 1283 | 279 | 1283 | 1283 |
soc-wiki-elec | 7061 | 7061 | 7061 | 7061 | 7061 | 7061 | 7061 | 7061 |
soc-advogato | 5014 | 5014 | 5014 | 5014 | 5014 | 5014 | 5014 | 5014 |
soc-pages | 10,095 | 10,095 | 10,029 | 1485 | 10,184 | 1485 | 10,184 | 10,184 |
soc-anybeat | 12,538 | 12,538 | 12,538 | 12,538 | 12,538 | 12,538 | 12538 | 12,538 |
soc-pages-sport | 13,739 | 13,739 | 13,739 | 13,739 | 13,739 | 13,739 | 13,739 | 13739 |
soc-epinions | 2094 | 3106 | 25,283 | 25,283 | 25,283 | 25,283 | 25,283 | 3106 |
soc-pages-media | 26,982 | 26,981 | 26,981 | 26,981 | 26,981 | 26,981 | 26,981 | 26,981 |
soc-pages-company | 1065 | 12,432 | 12,432 | 163 | 12,432 | 12,432 | 12,432 | 12,432 |
soc-gamesec-RO | 219 | 219 | 554 | 555 | 219 | 554 | 219 | 219 |
Instance name | BC | CC | DC | EC | HADC | EADC (\(\alpha =0.25\)) | EADC (\(\alpha =0.5\)) | EADC (\(\alpha =0.75\)) |
---|---|---|---|---|---|---|---|---|
soc-gplus | 14,556 | 14,556 | 14,556 | 14,556 | 14,556 | 14,556 | 14,556 | 14,556 |
Twitter Lists | 473 | 912 | 452 | 522 | 912 | 912 | 912 | 912 |
soc-hamsterer | 1666 | 1666 | 1666 | 1666 | 1666 | 1666 | 1666 | 1666 |
soc-pages-government | 3372 | 3372 | 3372 | 1446 | 3372 | 3372 | 3372 | 3372 |
soc-pages-politician | 552 | 552 | 652 | 387 | 552 | 552 | 552 | 552 |
soc-pages-shows | 297 | 297 | 299 | 141 | 297 | 196 | 297 | 297 |
soc-wiki-elec | 7061 | 7061 | 7061 | 7061 | 7061 | 7061 | 7061 | 7061 |
soc-advogato | 4667 | 4667 | 4667 | 4667 | 4667 | 4667 | 4667 | 4667 |
soc-pages | 1143 | 1143 | 7825 | 1328 | 1223 | 1328 | 1223 | 1223 |
soc-anybeat | 12,287 | 12,,287 | 12,287 | 12,287 | 12,287 | 12,287 | 12287 | 12287 |
soc-pages-sport | 1082 | 1082 | 1082 | 1082 | 1082 | 1082 | 1082 | 1082 |
soc-epinions | 1383 | 1824 | 22,581 | 22,581 | 22,581 | 22,581 | 22,581 | 1824 |
soc-pages-media | 1101 | 1189 | 1694 | 1694 | 1694 | 1694 | 1694 | 1694 |
soc-pages-company | 467 | 561 | 561 | 121 | 561 | 561 | 561 | 561 |
soc-gamesec-RO | 129 | 129 | 180 | 175 | 129 | 180 | 129 | 129 |
Instance name | BC | CC | DC | EC | HADC | EADC (\(\alpha =0.25\)) | EADC (\(\alpha =0.5\)) | EADC (\(\alpha =0.75\)) |
---|---|---|---|---|---|---|---|---|
soc-gplus | 11,482 | 11,482 | 11,,482 | 11,482 | 11,482 | 11,482 | 11,482 | 11,482 |
Twitter Lists | 473 | 850 | 452 | 522 | 850 | 850 | 850 | 850 |
soc-hamsterer | 1091 | 1091 | 1091 | 1091 | 1091 | 1091 | 1091 | 1091 |
soc-pages-government | 2631 | 2631 | 2631 | 1094 | 2631 | 2631 | 2631 | 2631 |
soc-pages-politician | 483 | 483 | 640 | 380 | 483 | 483 | 483 | 483 |
soc-pages-shows | 218 | 218 | 216 | 137 | 218 | 172 | 218 | 218 |
soc-wiki-elec | 7061 | 7061 | 7061 | 7061 | 7061 | 7061 | 7061 | 7061 |
soc-advogato | 4584 | 4584 | 4584 | 4584 | 4584 | 4584 | 4584 | 4584 |
soc-pages-public-figure | 905 | 905 | 958 | 1242 | 831 | 1242 | 831 | 831 |
soc-anybeat | 12,221 | 12,221 | 12,221 | 12,221 | 12,221 | 12,221 | 12,221 | 12,221 |
soc-pages-sport | 837 | 837 | 837 | 837 | 837 | 837 | 837 | 837 |
soc-epinions | 1310 | 1715 | 1709 | 1709 | 1709 | 1709 | 1709 | 1715 |
soc-pages-media | 911 | 984 | 1159 | 1159 | 1159 | 1159 | 1159 | 1159 |
soc-pages-company | 417 | 492 | 492 | 101 | 492 | 492 | 492 | 492 |
soc-gamesec-RO | 124 | 124 | 158 | 159 | 124 | 158 | 124 | 124 |
Instance name | BC | CC | DC | EC | HADC | EADC (\(\alpha =0.25\)) | EADC (\(\alpha =0.5\)) | EADC (\(\alpha =0.75\)) |
---|---|---|---|---|---|---|---|---|
soc-gplus | 8741 | 8741 | 8741 | 8741 | 8741 | 8741 | 8741 | 8741 |
Twitter Lists | 402 | 633 | 417 | 500 | 633 | 633 | 633 | 633 |
soc-hamsterer | 567 | 567 | 567 | 567 | 567 | 567 | 567 | 567 |
soc-pages-government | 1712 | 1712 | 1712 | 944 | 1712 | 1712 | 1712 | 1712 |
soc-pages-politician | 334 | 334 | 558 | 340 | 334 | 334 | 334 | 334 |
soc-pages-shows | 161 | 161 | 161 | 124 | 161 | 150 | 161 | 161 |
soc-wiki-elec | 5241 | 5241 | 5241 | 5241 | 5241 | 5241 | 5241 | 5241 |
soc-advogato | 1795 | 1795 | 1795 | 1795 | 1795 | 1795 | 1795 | 1795 |
soc-pages-public-figure | 498 | 498 | 570 | 1062 | 508 | 1062 | 508 | 508 |
soc-anybeat | 10130 | 10130 | 10130 | 10130 | 10130 | 10130 | 10130 | 10130 |
soc-pages-sport | 633 | 633 | 633 | 633 | 633 | 633 | 633 | 633 |
soc-epinions | 897 | 1107 | 981 | 981 | 981 | 981 | 981 | 1107 |
soc-pages-media | 640 | 724 | 863 | 863 | 863 | 863 | 863 | 863 |
soc-pages-company | 275 | 326 | 326 | 95 | 326 | 326 | 326 | 326 |
soc-gamesec-RO | 101 | 101 | 119 | 121 | 101 | 119 | 101 | 101 |
Instance name | BC | CC | DC | EC | HADC | EADC (\(\alpha =0.25\)) | EADC (\(\alpha =0.5\)) | EADC (\(\alpha =0.75\)) |
---|---|---|---|---|---|---|---|---|
soc-gplus | 11,990.96 | 11,990.96 | 11,990.96 | 11,990.96 | 11,990.96 | 11,990.96 | 11,990.96 | 11,990.96 |
Twitter Lists | 671.22 | 1298.42 | 697.3 | 592.26 | 1298.42 | 1298.42 | 1298.42 | 1298.42 |
soc-hamsterer | 1242.72 | 1242.72 | 1242.72 | 1242.72 | 1242.72 | 1242.72 | 1242.72 | 1242.72 |
soc-pages-government | 4027.29 | 4027.29 | 4027.29 | 2916.12 | 4027.29 | 4027.29 | 4027.29 | 4027.29 |
soc-pages-politician | 1907.98 | 1907.98 | 1123.45 | 724.17 | 1907.98 | 1907.98 | 1907.98 | 1907.98 |
soc-pages-shows | 748.47 | 748.47 | 743.79 | 253.3 | 748.47 | 347.11 | 748.47 | 748.47 |
soc-wiki-elec | 6623.02 | 6623.02 | 6623.02 | 6623.02 | 6623.02 | 6623.02 | 6623.02 | 6623.02 |
soc-advogato | 3741.1 | 3741.1 | 3741.1 | 3741.1 | 3741.1 | 3741.1 | 3741.1 | 3741.1 |
soc-pages-public-figure | 4415.09 | 4415.09 | 3928.15 | 2025.33 | 4535.9 | 2025.33 | 4535.9 | 4535.9 |
soc-anybeat | 11,394.31 | 11,394.31 | 11,394.31 | 11,394.31 | 11,394.31 | 11,394.31 | 11,394.31 | 11,394.31 |
soc-pages-sport | 4064.69 | 4064.69 | 4064.69 | 4064.69 | 4064.69 | 4064.69 | 4064.69 | 4064.69 |
soc-epinions | 6660.87 | 8353.97 | 7469.31 | 7469.31 | 7469.31 | 7469.31 | 7469.31 | 8353.97 |
soc-pages-media | 7927.39 | 10,118.52 | 10,916.34 | 10,916.34 | 10,916.34 | 10,916.34 | 10,916.34 | 10,916.34 |
soc-pages-company | 1644.77 | 2429.62 | 2429.62 | 161.55 | 2429.62 | 2429.62 | 2429.62 | 2429.62 |
soc-gamesec-RO | 1101.8 | 1101.8 | 1293.95 | 1235.01 | 1101.8 | 1293.95 | 1101.8 | 1101.8 |
Instance name | BC | CC | DC | EC | HADC | EADC (\(\alpha =0.25\)) | EADC (\(\alpha =0.5\)) | EADC (\(\alpha =0.75\)) |
---|---|---|---|---|---|---|---|---|
soc-gplus | 14,487.1 | 14,472.36 | 14,481.01 | 14,480.63 | 14,472.88 | 14,480.8 | 14,487.43 | 14,477.27 |
Twitter Lists | 11,989.12 | 11,955.72 | 11,992.85 | 11,964.66 | 11,906.41 | 11,917.2 | 11,916.64 | 11,908.19 |
soc-hamsterer | 937.39 | 937.74 | 938.05 | 936.18 | 937.11 | 937.69 | 936.21 | 937.34 |
soc-pages-government | 3148.14 | 3149.21 | 3148.54 | 3077.98 | 3150.89 | 3152.66 | 3140.53 | 3144.39 |
soc-pages-politician | 2771.62 | 2769.67 | 2640.67 | 2586.06 | 2770.33 | 2771.98 | 2769.76 | 2774.51 |
soc-pages-shows | 1437.09 | 1442.95 | 1431.11 | 1308.85 | 1444.45 | 1330.98 | 1445.35 | 1446.3 |
soc-wiki-elec | 2060.71 | 2062.82 | 2061.5 | 2061.38 | 2061.32 | 2061.22 | 2061.67 | 2061.75 |
soc-advogato | 2508.59 | 2504.19 | 2505.09 | 2503.53 | 2504.48 | 2506.25 | 2505.2 | 2503.19 |
soc-pages-public-figure | 4951.71 | 4949.31 | 4955.46 | 4792.01 | 4938.83 | 4792.36 | 4946.97 | 4940.21 |
soc-anybeat | 5989.9 | 5992.17 | 5990.56 | 5989.8 | 5989.71 | 5991.55 | 5994.93 | 5991.79 |
soc-pages-sport | 7147.25 | 7147.66 | 7142.17 | 7149.91 | 7146.72 | 7150 | 7149.07 | 7143.33 |
soc-epinions | 8131.74 | 8083.85 | 7971.35 | 7966.32 | 7972.66 | 7963.08 | 7967.07 | 8074.81 |
soc-pages-media | 13272.46 | 13217.94 | 13071.14 | 13069.32 | 13068.38 | 13071.39 | 13067.68 | 13075.13 |
soc-pages-company | 7085.8 | 7027.44 | 7036.72 | 6951.13 | 7038.37 | 7033.11 | 7033.63 | 7030.34 |
soc-gamesec-RO | 23,789.15 | 23,782.03 | 23,757.48 | 23,762.35 | 23,795.5 | 23,748.52 | 23,793.17 | 23,783.46 |
Instance name | HADC | \(\hbox {EADC}(\alpha =0.25)\) | \(\hbox {EADC}(\alpha =0.75)\) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
BC | CC | DC | EC | BC | CC | DC | EC | BC | CC | DC | EC | |
soc-gplus | 0.2877 | 0.17 | 0.1634 | 0.0384 | 0.2871 | 0.2403 | 0.1921 | 0.173 | 0.2725 | 0.172 | 0.1522 | 0.0793 |
Twitter Lists | 0.0645 | 0.0315 | 0.0898 | \(-\) 0.0034 | 0.0639 | 0.0169 | 0.099 | 0.0837 | 0.0727 | 0.0661 | 0.102 | \(-\) 0.0006 |
soc-hamsterer | 0.6595 | 0.7512 | 0.5876 | 0.6986 | 0.6472 | 0.7308 | 0.5757 | 0.6972 | 0.6636 | 0.7626 | 0.5742 | 0.6985 |
soc-pages-government | 0.2753 | 0.296 | 0.3775 | 0.2483 | 0.2745 | 0.2877 | 0.3669 | 0.2698 | 0.2533 | 0.2903 | 0.3761 | 0.2698 |
soc-pages-politician | 0.2079 | 0.197 | 0.2818 | 0.181 | 0.222 | 0.2039 | 0.3028 | 0.1982 | 0.182 | 0.1879 | 0.2883 | 0.1859 |
soc-pages-shows | 0.1713 | 0.199 | 0.274 | 0.1608 | 0.2047 | 0.2167 | 0.3236 | 0.1685 | 0.1708 | 0.1917 | 0.2544 | 0.1736 |
soc-wiki-elec | \(-\) 0.0191 | 0.0974 | \(-\) 0.0035 | 0.064 | \(-\) 0.0015 | 0.082 | 0.0027 | 0.0796 | 0.0003 | 0.0938 | 0.0087 | 0.0562 |
soc-advogato | 0.4419 | 0.4772 | 0.399 | 0.47 | 0.4399 | 0.4628 | 0.3957 | 0.4805 | 0.4412 | 0.466 | 0.3936 | 0.4725 |
soc-pages | 0.2768 | 0.2789 | 0.3643 | 0.2843 | 0.2943 | 0.2847 | 0.4008 | 0.2936 | 0.2763 | 0.2787 | 0.3667 | 0.2821 |
soc-anybeat | 0.2006 | 0.249 | 0.1857 | 0.1463 | 0.1947 | 0.2019 | 0.1701 | 0.1928 | 0.2 | 0.2239 | 0.1968 | 0.1547 |
soc-pages-sport | 0.2465 | 0.2275 | 0.2731 | 0.2186 | 0.2707 | 0.2239 | 0.2965 | 0.2188 | 0.2439 | 0.2202 | 0.2808 | 0.2081 |
soc-epinions | 0.5778 | 0.7117 | 0.6392 | 0.7523 | 0.5796 | 0.7237 | 0.6466 | 0.7593 | 0.58 | 0.7151 | 0.6388 | 0.7506 |
soc-pages-media | 0.2499 | 0.2552 | 0.3333 | 0.2567 | 0.2414 | 0.2564 | 0.3372 | 0.257 | 0.2411 | 0.2528 | 0.3287 | 0.2521 |
soc-pages-company | 0.2085 | 0.2026 | 0.2759 | 0.1866 | 0.2353 | 0.2012 | 0.3035 | 0.1905 | 0.2208 | 0.184 | 0.2797 | 0.186 |
soc-wiki-Vote | 0.0427 | 0.0754 | 0.033 | 0.1052 | 0.0553 | 0.0186 | 0.0237 | 0.0325 | 0.0444 | 0.0915 | 0.0764 | 0.0259 |
soc-gamesec-RO | 0.1859 | 0.1727 | 0.2366 | 0.1531 | 0.1956 | 0.1738 | 0.2495 | 0.1644 | 0.1821 | 0.1596 | 0.2358 | 0.1644 |
Average correlation | 0.25 | 0.27 | 0.28 | 0.25 | 0.26 | 0.27 | 0.29 | 0.27 | 0.25 | 0.27 | 0.28 | 0.25 |
Standard deviation | 0.179 | 0.2052 | 0.175 | 0.2169 | 0.173 | 0.2078 | 0.1746 | 0.2074 | 0.1775 | 0.2051 | 0.1673 | 0.2183 |
Instance name | HADC | EADC (\(\alpha =0.25)\) | EADC (\(\alpha =0.75)\) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
BC | CC | DC | EC | BC | CC | DC | EC | BC | CC | DC | EC | |
soc-gplus | 0.1793 | 0.2636 | 0.0768 | 0.1842 | 0.2025 | 0.2167 | 0.1011 | 0.2355 | 0.1839 | 0.2248 | 0.0778 | 0.1804 |
Twitter Lists | 0.0607 | 0.0461 | 0.0450 | 0.0188 | 0.0563 | 0.0635 | 0.0497 | \(-\)0.0099 | 0.0582 | 0.0874 | 0.0487 | 0.0208 |
soc-hamsterer | 0.4476 | 0.5573 | 0.4136 | 0.4890 | 0.4483 | 0.5265 | 0.4016 | 0.4805 | 0.4567 | 0.5652 | 0.4068 | 0.4906 |
soc-pages-government | 0.1699 | 0.1924 | 0.2295 | 0.1636 | 0.1680 | 0.1900 | 0.2392 | 0.1764 | 0.1749 | 0.1821 | 0.2331 | 0.1516 |
soc-pages-politician | 0.1352 | 0.1429 | 0.1958 | 0.1225 | 0.1315 | 0.1314 | 0.2033 | 0.1258 | 0.1278 | 0.1268 | 0.1837 | 0.1106 |
soc-pages-shows | 0.1094 | 0.1164 | 0.1808 | 0.1192 | 0.1262 | 0.1222 | 0.2122 | 0.1116 | 0.1094 | 0.1274 | 0.1838 | 0.0982 |
soc-wiki-elec | \(-\) 0.0064 | 0.0609 | 0.0120 | 0.0358 | \(-\)0.0036 | 0.0497 | 0.0079 | 0.0427 | 0.0063 | 0.0334 | 0.0106 | 0.0476 |
soc-advogato | 0.3235 | 0.3516 | 0.2779 | 0.3425 | 0.3255 | 0.3522 | 0.2835 | 0.3432 | 0.3260 | 0.3403 | 0.2767 | 0.3453 |
soc-pages-public-figure | 0.1880 | 0.1894 | 0.2480 | 0.1820 | 0.2010 | 0.1924 | 0.2586 | 0.1868 | 0.1986 | 0.1915 | 0.2473 | 0.1846 |
soc-anybeat | 0.1470 | 0.2268 | 0.1045 | 0.0746 | 0.1431 | 0.2182 | 0.1275 | 0.0775 | 0.1449 | 0.2153 | 0.1064 | 0.0729 |
soc-pages-sport | 0.1655 | 0.1482 | 0.1949 | 0.1383 | 0.1623 | 0.1485 | 0.1973 | 0.1481 | 0.1651 | 0.1488 | 0.1865 | 0.1466 |
soc-epinions | 0.4176 | 0.5375 | 0.4658 | 0.5739 | 0.4232 | 0.5336 | 0.4650 | 0.5785 | 0.4167 | 0.5363 | 0.4685 | 0.5720 |
soc-pages-media | 0.1666 | 0.1631 | 0.2204 | 0.1669 | 0.1689 | 0.1680 | 0.2239 | 0.1756 | 0.1731 | 0.1696 | 0.2200 | 0.1710 |
soc-pages-company | 0.1400 | 0.1294 | 0.1836 | 0.1207 | 0.1397 | 0.1294 | 0.1898 | 0.1198 | 0.1455 | 0.1344 | 0.1833 | 0.1148 |
soc-gamesec-RO | 0.1232 | 0.1093 | 0.1590 | 0.1010 | 0.1273 | 0.1142 | 0.1618 | 0.1026 | 0.1280 | 0.1116 | 0.1576 | 0.1023 |
Average correlation | 0.1845 | 0.2157 | 0.2005 | 0.1889 | 0.1880 | 0.2104 | 0.2082 | 0.1930 | 0.1877 | 0.2130 | 0.1994 | 0.1873 |
Standard deviation | 0.1227 | 0.1550 | 0.1230 | 0.1587 | 0.1233 | 0.1484 | 0.1191 | 0.1604 | 0.1229 | 0.1539 | 0.1224 | 0.1592 |
Instance name | HADC | \(\hbox {EADC}(\alpha =0.25)\) | \(\hbox {EADC}(\alpha =0.75)\) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
BC | CC | DC | EC | BC | CC | DC | EC | BC | CC | DC | EC | |
soc-gplus | 0.3873 | 0.9108 | 0.6125 | 0.7472 | 0.3751 | 0.8643 | 0.6025 | 0.7626 | 0.3938 | 0.9309 | 0.6151 | 0.7385 |
Twitter Lists | 0.5074 | 0.9006 | 0.3708 | 0.2617 | 0.5237 | 0.7576 | 0.4133 | 0.2822 | 0.5052 | 0.9161 | 0.3659 | 0.2599 |
soc-hamsterer | 0.6296 | 0.9318 | 0.7721 | 0.8624 | 0.6266 | 0.909 | 0.7797 | 0.8847 | 0.6317 | 0.9428 | 0.7679 | 0.8499 |
soc-pages-government | 0.3962 | 0.8576 | 0.6462 | 0.6835 | 0.3802 | 0.7979 | 0.6706 | 0.7401 | 0.4024 | 0.8853 | 0.6307 | 0.6543 |
soc-pages-politician | 0.4003 | 0.7377 | 0.5264 | 0.5629 | 0.3317 | 0.5951 | 0.6021 | 0.6447 | 0.4166 | 0.7894 | 0.4984 | 0.5246 |
soc-pages-shows | 0.3818 | 0.8164 | 0.6155 | 0.7474 | 0.351 | 0.7154 | 0.6712 | 0.766 | 0.3912 | 0.8449 | 0.5841 | 0.7176 |
soc-wiki-elec | 0.6856 | 0.9279 | 0.8281 | 0.9099 | 0.6869 | 0.92 | 0.8406 | 0.9223 | 0.6841 | 0.9296 | 0.8184 | 0.8993 |
soc-advogato | 0.6855 | 0.9322 | 0.7789 | 0.8504 | 0.6866 | 0.9156 | 0.7907 | 0.867 | 0.6842 | 0.9396 | 0.7724 | 0.8416 |
soc-pages-public-figure | 0.4086 | 0.4934 | 0.7131 | 0.563 | 0.2974 | 0.3305 | 0.7534 | 0.7474 | 0.4504 | 0.5715 | 0.6575 | 0.478 |
soc-anybeat | 0.489 | 0.9049 | 0.7134 | 0.8538 | 0.4863 | 0.893 | 0.7156 | 0.863 | 0.4909 | 0.9122 | 0.7118 | 0.8467 |
soc-pages-sport | 0.554 | 0.9609 | 0.5484 | 0.7228 | 0.5641 | 0.9344 | 0.5653 | 0.7328 | 0.551 | 0.9646 | 0.5438 | 0.7191 |
soc-epinions | 0.4379 | 0.7928 | 0.7482 | 0.7065 | 0.4086 | 0.739 | 0.7541 | 0.7644 | 0.4508 | 0.8176 | 0.7389 | 0.6782 |
soc-pages-media | 0.5299 | 0.8232 | 0.6674 | 0.8256 | 0.5213 | 0.7871 | 0.6852 | 0.8472 | 0.5327 | 0.8369 | 0.6599 | 0.8169 |
soc-pages-company | 0.5619 | 0.95 | 0.5353 | 0.2957 | 0.5618 | 0.9123 | 0.5564 | 0.3019 | 0.5614 | 0.9566 | 0.531 | 0.2948 |
soc-gamesec-RO | 0.5634 | 0.9371 | 0.4429 | 0.4533 | 0.567 | 0.8887 | 0.4712 | 0.4845 | 0.5634 | 0.9401 | 0.4402 | 0.4483 |
Average correlation | 0.5079 | 0.8585 | 0.6346 | 0.6697 | 0.4912 | 0.7973 | 0.6581 | 0.7074 | 0.5140 | 0.8785 | 0.6224 | 0.6512 |
Standard deviation | 0.1056 | 0.1203 | 0.1309 | 0.2032 | 0.1276 | 0.1617 | 0.1220 | 0.1998 | 0.0994 | 0.1007 | 0.1300 | 0.2049 |