Measuring the Influence Between Individuals in Large-Scale Social Networks

Most of this post is excerpted from the PhD thesis of Jing ZHANG, a “Paper Machine” in our lab, (https://xiaojingzi.github.io/). It relates to our submitted paper Panther: Fast Top-k Similarity Search in Large Networks, and the original can be found here. The goal here is to casually introduce some ideas for quickly measuring influence between individuals in large-scale social network structural data to anyone who happens to stumble across this page. If you are interested in reading the original paper and it proves useful for your current work, that would be wonderful.

The premise of this post is that the input consists only of large-scale social network structure. The reason user behavior data is ignored is that in some scenarios such data is not easy to obtain. Under this premise, we first need to define influence between individuals. Similarity and influence are two factors that researchers have long tried to distinguish as drivers of user behavior; however, in most cases it is not easy to tell whether it is similarity or influence that drives a user’s actions. In the absence of user behavior data, we can approximate influence by similarity. The basic idea is that the higher the network similarity between two nodes, the stronger the mutual influence between them. Therefore, this chapter is essentially about solving the problem of computing node similarity in large-scale social networks.

Computing node similarity is a fundamental problem in network analysis and the core of many data mining algorithms such as clustering, graph matching, and object retrieval. In general, measuring the similarity between two nodes in a network can follow two different principles. The first principle says that two nodes are similar if and only if their neighbors are similar. The second principle says that two nodes are similar if and only if their social roles or social statuses are equivalent, where social role or status can be measured by network characteristics such as centrality, closeness, and clustering coefficient. Usually, nodes found similar under the first principle are relatively close to each other in distance, so this is called neighborhood similarity. Nodes found similar under the second principle have no relation to distance; they may even be two completely disconnected nodes, yet be very similar in topological structure, so this is called structural similarity. Although computing similarity between nodes in a network has been studied extensively—for example, SimRank is the canonical method for neighborhood similarity. Its basic idea is that two nodes are similar if and only if their neighbor nodes are similar, so the algorithm is essentially an iterative method. ReFex is the canonical method for structural similarity. Its basic idea is that two nodes are similar if and only if their network characteristics are similar, such as centrality and the average or sum of centralities of one-hop, two-hop, and three-hop indirect neighbors. However, traditional methods are generally very inefficient. For example, the time complexity of SimRank is $O(I|V|^2d^2)$, where I is the number of iterations, |V| is the number of nodes in the network, and d is the average node degree. ReFex is also an iterative algorithm, and its time complexity grows exponentially as the explored neighbor degree increases. In recent years a number of acceleration methods have emerged, but they generally only speed up neighborhood similarity—for example, Lee et al. proposed an algorithm that can quickly compute the k nodes with the highest SimRank similarity to any given node. However, there has been almost no research on accelerating structural similarity. Therefore, the research goal of this chapter is to design a similarity computation method that can uniformly and quickly compute both neighborhood similarity and structural similarity.

Our research idea is to propose a sampling algorithm called Panther that can quickly compute neighborhood similarity between nodes in a network. The innovation of this algorithm lies in random path sampling. Specifically, given a network, we perform R random walks. Each time, a starting node is randomly selected and a random walk of T steps is executed. The basic idea is that the more paths two nodes co-occur on, the more similar they are. Theoretically, it can be proved that when the number of sampled paths reaches $R = \frac{c}{\varepsilon^2} (log_2(_2^T) +1 + ln \frac{1}{n} )$, the result can be obtained with error rate ε at probability 1−η. Furthermore, in order to compute similarity between distant or even disconnected nodes, we extend each node with a vector representing its structural features on the basis of the Panther algorithm. We name this extended algorithm Panther++.

We use the Tencent Weibo follow network to verify the efficiency and effectiveness of the proposed methods. The results show that on a Tencent Weibo network with 443,070 nodes and 5,000,000 edges, Panther and Panther++ are about 300× faster than the fastest comparison method. At the same time, the proposed methods scale well: on a Tencent Weibo network with 51,640,620 nodes and 1,000,000,000 edges, finding the top-5 most similar nodes for each node takes an average of 0.0001 seconds per node.

Finally, an implementation based on this paper can be obtained here:

[github_widget repo="yuikns/panther"]