CN108833211A - Unbiased Delayed Sampling Method for Social Networks - Google Patents

Abstract

The invention discloses a data sampling method (unbiased delay sampling) of a social network. The method follows the Markov convergence criterion, and the unbiased sampling method can adapt to networks with different degrees of network usage. On the one hand, the unbiased delay method has better On the other hand, the unbiased delay sampling method can reduce the sampling probability of repeated data and improve the detection ability of the network.

Description

Unbiased Delayed Sampling Method for Social Networks

technical field

The present invention relates to the technical field of social network data sampling, in particular to a social network unbiased-delay sampling method (Unbiased-delay sampling, UD Sampling).

Background technique

In recent years, online social networking has become a major Internet service. The vigorous development of social networks has attracted the attention of a large number of researchers. Sociologists want to study the user behavior of online users. Engineers use social networks to design better network systems. Researchers study the structure and dynamic change process of this complex network. .

Social networks are usually modeled as social graphs for research and analysis. The problem that researchers directly face is that the amount of data in social networks is too large. First, it is impractical to obtain a complete dataset, because capturing such a large social graph would take unimaginably time-consuming and sometimes impossible. At the same time, processing such a huge social graph requires a lot of time for calculation even with high-performance computer clusters. Second, due to commercial confidentiality and users' private settings, the complete data of social networks is not available. Finally, the number of users of social networks grows rapidly and the relationships between users change over time, so classically large networks cannot be fully crawled. Therefore, how to capture an appropriate amount of samples in a large network and maintain the network properties of the original network has become the basic problem of social network research.

Currently commonly used network sampling technology generally applies the breadth-first search algorithm for data sampling. Although the breadth-first search algorithm can quickly obtain a large amount of user data. However, in actual production, it is necessary to consume a lot of resources to design the deduplication queue, which will greatly reduce the efficiency of data extraction. At the same time, the breadth-first search algorithm is a typical network traversal algorithm, and the data extracted by the algorithm will be biased towards high-level nodes, so this method cannot obtain reliable user data.

Contents of the invention

In order to solve the shortcomings of the existing social network data extraction schemes that cannot obtain unbiased data and need to design deduplication queues, the present invention provides a novel network sampling method (unbiased sampling method), so that more reliable unbiased data can be obtained.

The present invention adopts following technical scheme: a kind of unbiased delay sampling method of social network, comprises the following steps:

(1) Transform the real network into a graph G=(E, V), E represents the set of edges in the graph, the edges represent the relationship between users in the real network, V represents the set of nodes in the graph, and the nodes represent the real network users under .

(2) Initialize the sampling set S, cache space Cache, and empty S and Cache; randomly select a node v from V; then follow the steps below to sample.

(3) Detect 10 neighbor nodes of node v, and detect all neighbor nodes for nodes whose neighbor number is less than 10. Store the detected neighbor nodes in the cache space Cache.

(4) Randomly select a neighbor node w among all neighbor nodes of node v. Determine whether K _v /K _w is greater than or equal to P, if yes, take the neighbor node w as the current node v, and put node w into the sampling set S, then return to step 3, if not, continue to the next step. Among them, P is a random number, and P obeys the uniform distribution of 0-1. K _v represents the number of neighbor nodes of node v, that is, the degree of node v.

(5) Determine whether P is less than or equal to the probability α of repeated sampling, if yes, keep the current node v unchanged, and then return to step 3, if not, continue to the next step.

(6) Find all detected nodes with the same number of neighbors as the current node v in the cache space Cache, and select a node with the smallest number of detections from these detected nodes There are multiple nodes with the same number of probes to choose a random one. will node As the current node v, and the node Put in the sample set and return to step 3.

Further, in the step 5, α=0.2.

The beneficial effects of the present invention are: firstly, on an independent sampling set, the degree distribution properties of the network are closer to the original network characteristics. Second, it avoids the problem of excessive sampling of low-degree nodes in high-connected subnetworks in traditional methods, and improves the detection ability of the method for the network. Third, in the case of low sampling rate, the transitivity and assortativeness of its samples are closer to the properties of the original network.

Description of drawings

Figure 1 is the independent sampling node degree distribution CDF and NMSE graph of Twitter and Epinions;

Figure 2 is a transitive diagram of different sampling networks;

Figure 3 is the assortative diagram of different sampling networks;

Fig. 4 is an update rate diagram of a sampling node;

Fig. 5 is a graph showing the influence of parameter α on the sampling repetition rate.

Detailed ways

Step 1: Define the concept:

The research on social network sampling methods usually converts the real network into a graph model. The edges in the graph represent the relationship between users in the real network, and the nodes in the graph represent the users in the real network. A graph is represented using the notation G=(E,V), where E represents the set of edges in the graph, V represents the set of nodes in the graph, and v represents the nodes in the graph. The sampling set is defined as S. The nodes that have been detected during the sampling process will be pushed into the cache space, and the cache space is defined as Cache. The nodes in the cache space are represented by d, and d ^j represents the detected node, where j is the number of times the node has been detected, Indicates the detected nodes that have the same number of neighbors as node v. K _v represents the number of neighbor nodes of node v, that is, the degree of node v. α represents the probability of repeated sampling, which is 0.2 by default.

Step 2: Initialize the sampling set S, the cache space Cache, and empty S and Cache

Step 3: Select the initial node v, the selection method is to select randomly in the whole network.

Step 4: Detect 10 neighbor nodes of node v, if the number of neighbors is less than 10, detect all neighbor nodes. Store the detected node d ^j in the cache space Cache.

Step 5: Randomly select a neighbor node w among all neighbor nodes of node v.

Step 6: Generate a random number P between 0 and 1, and P obeys the uniform distribution of 0-1.

Step 7: Determine whether P is less than or equal to K _v /K _w , if yes, take the neighbor node w as the current node v, and put node w into the sampling set S, then go to step 5, if not, continue to the next step.

Step 8: Determine whether P is less than or equal to α (α is 0.2 by default), if yes, keep the current node v unchanged, and then go to step 5. If not, continue to the next step.

Step 9: Find the detected node set with the same number of neighbors as the current node v in the cache space Select a node with the smallest number of detections in this detected node set Among them, J=min(j), and there are multiple nodes with the same number of times of being detected to choose a random one. will node As the current node v, and the node Put in the sample set and go to step five.

The stop rule of the method can be artificially stopped when enough data is obtained, or it can be automatically stopped after a period of data extraction.

Here, Twitter and Epinions networks with different degrees of connectivity are used to evaluate the sampling performance of the unbiased delayed sampling method. The classic sampling methods involved in the comparison include BFS, MHRW, and RW.

From the left half of Fig. 1, it can be seen that the degree distribution of MHRW, BFS will be biased towards nodes with large degrees, because their NMSE curves are higher than those obtained by the UD method. At the same time, the degree distribution CDF curve obtained by the UD method is closer to the original network than other methods, which also shows that the degree distribution properties of the network collected by the UD method are closer to the original network degree distribution than the MHRW and BFS methods. In summary, the subnetworks collected by the UD method have better degree distribution properties, even if the sampled network has no repeated data.

In Figure 2, the black horizontal baseline represents the specific value of the transitivity of the original network statistics. It can be seen from the figure that as the sampling rate continues to increase, the transitivity of the sampling network of different sampling methods will tend to the baseline value , but in a smaller sampling ratio, the improved UD method is closer to the transitivity index of the original network than the MHRW and RW methods.

Figure 3 evaluates the network assortativeness metrics of the networks extracted by different sampling methods. It can be seen from the figure that the candidate sampling method quickly converges to the assortative property of the original network as the sampling rate increases. But at lower sampling rates, the improved UD method is closer to the baseline, indicating that the UD method has a better network assortment index than the MHRW and RW methods.

Figure 4 shows the sampled update rates for Twitter and Epinions. The horizontal axis represents the number of extracted independent nodes, and the vertical axis is the ratio of the number of extracted independent nodes to the actual number of sampled nodes, which is called the update rate. It is not difficult to find that a higher update rate has fewer duplicate nodes. Therefore, a higher update rate will have better network detection capabilities during the sampling process. It can be seen from Figure 4 that the sampling update rate of the sparse network (Epinions) is lower than that of the highly connected network (Twitter), and the sampling update rate of the UD method for networks with different connectivity is better than that of MHRW. This is because a network with low connectivity has a higher probability of reaching a node that has already been visited. This proves that the UD sampling method can avoid the over-sampling problem of MHRW in low-degree nodes, and at the same time, the UD method will have better network detection capabilities.

In the UD sampling process, we use the parameter value α to control the self-circulation probability of the current node. Figure 5 shows the influence of different parameter α on the repetition rate of the sampling node. Among them, the abscissa represents the value of the parameter α, α starts from 0.05 with a step size of 0.05 to 1 (α=0.05,0.1,0.15,…,1), and the ordinate represents the node repetition rate in the sampling set (all nodes in the sample The number of / the number of independent nodes in the sample). We use the UD method, MHRW and RW methods to collect 5% of the data in the Twitter dataset respectively. It can be seen from Fig. 5 that when the value of parameter α is close to 0, the sample repetition rate of UD sampling method is close to RW. When the value of parameter α is 1, the sample repetition rate of UD sampling method is 6 times that of RW and the same as that of MHRW. So in social networks, the parameter α can be used to control the sample repetition rate of the UD sampling method. More specifically, if the parameter α is between 0.2 and 0.4, the sampling repetition rate of MHRW will be better reduced.

Claims (2)

1. an unbiased delay sampling method of social network, is characterized in that, comprises the following steps: (1) Transform the real network into a graph G=(E, V), E represents the set of edges in the graph, the edges represent the relationship between users in the real network, V represents the set of nodes in the graph, and the nodes represent the real network users under . (2) Initialize the sampling set S, cache space Cache, and empty S and Cache; randomly select a node v from V; then follow the steps below to sample. (3) Detect 10 neighbor nodes of node v, and detect all neighbor nodes for nodes whose neighbor number is less than 10. Store the detected neighbor nodes in the cache space Cache. (4) Randomly select a neighbor node w among all neighbor nodes of node v. Determine whether K _v /K _w is greater than or equal to P, if yes, take the neighbor node w as the current node v, and put node w into the sampling set S, then return to step 3, if not, continue to the next step. Among them, P is a random number, and P obeys the uniform distribution of 0-1. K _v represents the number of neighbor nodes of node v, that is, the degree of node v. (5) Determine whether P is less than or equal to the probability α of repeated sampling, if yes, keep the current node v unchanged, and then return to step 3, if not, continue to the next step. (6) Find all detected nodes with the same number of neighbors as the current node v in the cache space Cache, and select a node with the smallest number of detections from these detected nodes There are multiple nodes with the same number of probes to choose a random one. will node As the current node v, and the node Put in the sample set and return to step 3. 2. The method according to claim 1, characterized in that, in the step 5, α=0.2.