Identifying influential nodes in large-scale directed networks: the role of clustering

Abstract

Identifying influential nodes in very large-scale directed networks is a big challenge relevant to disparate applications, such as accelerating information propagation, controlling rumors and diseases, designing search engines, and understanding hierarchical organization of social and biological networks. Known methods range from node centralities, such as degree, closeness and betweenness, to diffusion-based processes, like PageRank and LeaderRank. Some of these methods already take into account the influences of a node's neighbors but do not directly make use of the interactions among it's neighbors. Local clustering is known to have negative impacts on the information spreading. We further show empirically that it also plays a negative role in generating local connections. Inspired by these facts, we propose a local ranking algorithm named ClusterRank, which takes into account not only the number of neighbors and the neighbors' influences, but also the clustering coefficient. Subject to the susceptible-infected-recovered (SIR) spreading model with constant infectivity, experimental results on two directed networks, a social network extracted from delicious.com and a large-scale short-message communication network, demonstrate that the ClusterRank outperforms some benchmark algorithms such as PageRank and LeaderRank. Furthermore, ClusterRank can also be applied to undirected networks where the superiority of ClusterRank is significant compared with degree centrality and k-core decomposition. In addition, ClusterRank, only making use of local information, is much more efficient than global methods: It takes only 191 seconds for a network with about [Formula: see text] nodes, more than 15 times faster than PageRank.

Figure 1. The correlation between and the degree in the first network .

The area of a circle is proportional to the number of nodes with the corresponding degree.

Figure 2. The increment of degree in the period of nodes with the same degree () but different clustering coefficients at time .

is the average value of a bin (size = 0.1) on clustering coefficient. For example, the value of corresponding to is the average value of of the nodes with clustering coefficient in . The error bars stand for standard errors.

Figure 3. An example network with 38 nodes and 110 directed edges.

Although nodes 0 and 37 have the same out-degree, node 37 is of higher influence (subject to spreading dynamics) than node 0. The clustering coefficients of these two nodes are and .

Figure 4. for top- ranked nodes by out-degree centrality (squares), PageRank (diamond), LeaderRank (triangle) and ClusterRank (circles).

We set and . Each data point is obtained by averaging over 100 independent runs.

Figure 5. The ratio of the number of infected and recovered nodes by ClusterRank to those by out-degree centrality, PageRank and LeaderRank.

Initially only non-overlapped nodes in the top- lists obtained by ClusterRank and other ranking algorithms are set to be infected. We set and . Each data point is obtained by averaging over 100 independent runs.

Figure 6. The dependence of on parameter .

The initially infected nodes are the top-50 nodes obtained by out-degree centrality (squares), PageRank (diamonds), LeaderRank (triangles) and ClusterRank (circles). We set . Each data point is obtained by averaging over 100 independent runs.

Figure 7. The ratio of the number of final recovered nodes by ClusterRank to those by out-degree centrality, PageRank and LeaderRank.

The non-overlapped nodes in the top-50 lists are initially infected. We set . Each data point is obtained by averaging over 100 independent runs.

Figure 8. The dependance of on parameter in undirected Delicious and Cond-mat networks. We set .

In (a) and (c), the initial infected nodes are those non-overlapped nodes in the top-50 places regardless of whether they are connected or not. In (b) and (d), the initial infected nodes are the non-overlapped nodes in top-50 places under constraint that any two of them are not connected. Each data point is obtained by averaging over 100 independent runs.