CN103327075A - Distributed mass organization realizing method based on label interaction - Google Patents

Abstract

The invention discloses a distributed community discovery method based on tag interaction, which specifically includes: setting known information in an application scene, a network initialization process, and a tag update process. The method of the present invention is a general computing model. Under the condition that the global topology is unknown and the nodes only know the local topology information of one-hop logical relationship, the community relationship can be dynamically discovered and maintained; all nodes participate in the calculation, and through the label interaction between nodes To complete the community discovery process in a dynamic network environment, each node updates its own label number according to the policy by exchanging label information with its neighbor nodes, and does not care about the topology of the entire network.

Description

A Distributed Community Discovery Method Based on Tag Interaction

technical field

The invention belongs to the technical field of communication, and in particular relates to a community discovery method in a mobile social network.

Background technique

A community is a grouping of nodes in a network, with more edges within a group and fewer edges between groups. The community structure in a complex network is of great significance, because the community structure usually corresponds to a certain functional unit in the network, for example, a community composed of sites with the same theme in the World Wide Web; a community composed of cell units with the same function in a biological network. The process of discovering communities in complex networks can be seen as a coarser-grained process of complex networks, and discovering community structures can also reveal the role of a specific node in complex networks.

With the deepening of research, it is found that many real networks have a community structure, that is, the entire network is composed of several communities, the connections between the communities are relatively sparse, and the connections within the communities are relatively dense. Community discovery is to use the information contained in the graph topology to analyze its modular community structure from the complex network. The in-depth study of this problem helps to study the modules, functions and evolution of the entire network in a divide-and-conquer manner. , it is of great significance to understand the organization principles, topology and dynamics of complex systems more accurately.

Most of the community discovery methods in current research are centralized community discovery algorithms, that is, a server with a logical topology of the entire network can discover community structures in the entire network through various algorithms and strategies. There are currently two common distributed computing methods.

One is to calculate the same network data separately through different servers. Each server uses different algorithm parameters, and then performs statistical processing on the results to obtain the optimal community discovery results. This method would originally require multiple calculations. The algorithm for comparing the results is divided into pipelines for processing.

The other is to use the existing distributed computing model to realize the parallel processing of the community discovery algorithm. The CLPA (CliqueLabel Propagation Algorithm) algorithm uses this method to realize parallel computing. This method uses a programming model MapReduce proposed by Google. This model is mainly used for processing massive data. CLPA proposes to use this model to process data. Input, so that parallel computing can be realized, the calculation originally performed on one server is distributed to the server group for completion, and then the final result of the algorithm is obtained.

The essence of these two methods is to use the existing model for distributed calculation of the calculation content. The premise and content of the algorithm calculation have not changed. Both require a centralized server to provide the topology of the entire network for the distributed calculation steps. Information, community discovery is performed in a static network with a known topology of the entire network, that is, a server with a logical topology of the entire network discovers the community structure in the entire network through various algorithms and strategies.

Contents of the invention

The purpose of the present invention is to solve the above-mentioned problems existing in the prior art, and propose a distributed community discovery method based on tag interaction.

The technical solution of the present invention is: a distributed community discovery method based on label interaction, which specifically includes the following steps:

step 1. Set the known information in the application scenario, specifically including: the initialization label number of each node, and the label number is unique; the logical neighbors of each node;

Step 2. Network initialization process: All nodes in the network initialize their own label numbers according to local unique information; set the weight of the label number to 1, and initialize the propagation factor of the label number to 1; set the number of local iterations to 1, and send The node broadcasts its own label number; initializes the locally saved neighbor label number list, and sets each neighbor label in the saved neighbor label number list to an unupdated state;

Step 3. Label update process: The node receives the label number broadcast from the neighbor, compares the number of iterations in the received neighbor label number list with the iteration number of the corresponding neighbor label list saved locally, if the iteration number in the received neighbor label list is greater than the local If the number of neighbor list iterations saved, update the neighbor label list, set the status of the corresponding list as updated, if it is less than or equal to the number of iterations of the neighbor list saved locally, then ignore the broadcast message; when all the neighbor label numbers recorded by the node are updated When the flag is updated, update the list of local label numbers. The update strategy is: add the list of label numbers of the neighbors, and the propagation factor of the label is the largest propagation factor among the same labels of the neighbors minus the preset propagation coefficient p. If the label If the propagation factor is less than 0, delete the label; add the label weights of the same label number, normalize all label weights, delete the label number with a weight less than the preset parameter 1/v, and keep the one with the largest weight if it is less than 1/v Tag number, if there are multiple such tag numbers, randomly select a tag with the largest weight, delete the rest of the tags, then normalize the reserved tag numbers, add 1 to the number of iterations, and broadcast a new list of local tag numbers to the neighbors. The tag list update flags of all recorded neighbors are set to not updated; if the tag number list of the node does not change after an update, it indicates that the community structure to which the node belongs in the current state has been stabilized.

Further, the above method also includes a dynamic maintenance process. When a new node appears or the logical neighbor relationship between two nodes changes, the dynamic maintenance process is triggered. At this time, the node publishes its own label list to all neighbor nodes and initiates a label update. process.

Further, the local unique information described in step 2 is specifically a mac address or a user name or a node ID.

Beneficial effects of the present invention: The distributed community discovery method based on label interaction proposed by the present invention is a general computing model, and it can dynamically discover, Maintain the community relationship; all nodes participate in the calculation, and complete the community discovery process in the dynamic network environment through label interaction between nodes. Each node updates its own label number according to the strategy by exchanging label information with neighbor nodes. It does not care about the topology of the entire network. In the method of the present invention, each node participates in the calculation process of the community discovery algorithm, so it does not depend on a centralized server that knows the topology of the entire network, the nodes do not need to know the topology of the entire network, and the time complexity no longer becomes the bottleneck of the community discovery algorithm; In addition, in the tag update process, different update strategies can be used to achieve better community discovery results. Therefore, the method of the present invention can be used as a framework module to slightly modify all tag-based community discovery algorithms and apply it to different models. Therefore, it is suitable for distributed community discovery algorithms.

Description of drawings

Fig. 1 is the main flowchart of the specific embodiment of the present invention.

Fig. 2 is a specific flow chart of Step 2 of a specific embodiment of the present invention.

Fig. 3 is a specific flow chart of Step 3 of a specific embodiment of the present invention.

Fig. 4 is a specific flow chart of Step 4 of a specific embodiment of the present invention.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings and specific embodiments. As shown in Figure 1, the distributed community discovery method based on label interaction includes the following steps:

step 1. Set the known information in the application scenario:

Distributed community discovery algorithms require certain scene capabilities and network environments. Before the method is initialized, the information that can be known in the application scene includes:

Let each node know its initial label number, and the label number is unique; let each node know which logical neighbors it has.

Here, each node perceives the appearance and disappearance of its neighbor nodes by exchanging information with neighbor nodes in real time.

Step 2. Network initialization process:

All nodes in the network initialize their own label numbers according to the local unique information; the local unique information can use any one of identifiers such as mac address, user name, and node ID. Set the weight of the label number to 1, set the propagation factor of the label number to 1; set the number of local iterations to 1, and broadcast its own label number to all neighbor nodes. The detailed process of this step is shown in Figure 2:

Step 21. All nodes initialize their own tag numbers: All nodes in the network initialize their own tag numbers based on local unique information, which can be identified by mac address, user name, node ID, etc.

Step 22. Set the weight of the tag number to 1, and initialize the propagation factor to 1.

Step 23. Set the number of local iterations to 1.

Step 24. Broadcast its own label number to all neighbor nodes.

Step 25. Initialize the list of neighbor label numbers saved locally, and set each neighbor label number in the saved neighbor label number list as an unupdated state.

Step 3. Tag update process:

The node receives the label number broadcast from the neighbor, compares the number of iterations in the received neighbor label list with the iteration number of the corresponding neighbor label list saved locally, and if the label number is greater than the number of iterations of the saved neighbor list, update the neighbor label list , set the status of the corresponding list as updated, if it is less than or equal to the number of iterations of the locally saved neighbor list, ignore the broadcast message; when the update flags of all neighbor label numbers recorded by the node are updated, update the local label number list, The update strategy is: add up the label lists of the neighbors, and the propagation factor of the label is the largest propagation factor among the neighbors with the same label minus the fixed propagation coefficient p. If the label propagation factor is less than 0, delete the label. Add the weights of the same tag numbers, normalize the weights of all tag numbers, delete the tag numbers whose weight is less than the predetermined parameter 1/v, if they are all less than 1/v, keep the tag number with the largest weight, if there are multiple such tag numbers , then randomly select a label with the largest weight, delete the remaining labels, and then normalize the weight value of the reserved label number, increase the number of iterations by 1, broadcast a new list of label numbers to neighbors, and update the label list of all recorded neighbors Set to not updated. v is a pre-set parameter, representing the maximum number of communities (state machine) that a node belongs to.

During the label update process, the label number in the label list retained by each node represents the community structure id to which the current node belongs. If the label number list of the node does not change after an update, it proves that the node is in the current state. The community structure of affiliation has stabilized. There will be no change until the community relationship changes or the community affiliation changes due to the change of the neighbor's community relationship.

It should be noted that the information carried by a label number here includes: label number, label number weight, propagation factor and other information; each node has a local label number list, which is composed of multiple label numbers (initialization, each node Corresponding to a tag number, in the subsequent process, that is, during the tag update process, the node can save multiple tag numbers), representing the tag numbers it owns, and the information of the local tag number list includes: the number of local iterations, and multiple tag numbers ;When a node broadcasts its own label number list, what it broadcasts is a local label number list, including the number of local iterations and multiple label numbers; each node also maintains a label number list of its neighbors, which includes multiple tables, each A neighbor corresponds to a tag number list, and the tag number list of each neighbor contains information: the number of iterations of the neighbor, the tag number owned by the neighbor, and the tag number update status of the neighbor.

The specific steps are shown in Figure 3:

Step 31. The node receives and records the label number broadcast from the neighbor: compare the number of iterations in the received neighbor label list with the iteration number of the corresponding neighbor label list saved locally, if the label number is greater than the number of iterations of the neighbor list saved this time, Then update the neighbor label list, set the status of the corresponding list as updated, if it is less than or equal to the number of iterations of the neighbor list saved locally, then ignore the broadcast message; when the update flags of all neighbor label numbers recorded by the node are updated, update A list of local tag numbers.

Step 32. Select to update the label number: add the neighbor's label list, add the weights of the same label, normalize all label weights, delete the label numbers whose weight is less than the predetermined parameter 1/v, and keep them if they are all less than 1/v The tag number with the largest weight. If there are multiple such tag numbers, randomly select a tag with the largest weight, delete the rest of the tags, and then normalize the reserved tag numbers. The propagation factor of the label number is set to the result of subtracting the propagation coefficient p from the maximum value of the propagation factor of the same label number in the neighbor label list, and the label number with a propagation factor less than 0 is deleted. Among them, v is a preset parameter, which represents the maximum number of communities that a node belongs to; p is a preset parameter, which represents the speed attenuation of the propagation factor, and is a real number in the interval [0, 1].

Step 33. Accumulate the number of iterations and broadcast a new list of label numbers to neighbors: add 1 to the number of iterations, broadcast a new list of label numbers to neighbors, and set the label list update flags of all recorded neighbors to not updated.

Step 34. Check whether the label number list of the node has changed: during the label update process, the label number in the label list retained by each node represents the community structure id to which the current node belongs. If after an update, the node's label If the number list has not changed, it proves that the community structure that the node belongs to in the current state has been stabilized. There will be no change until the community relationship changes or the community affiliation changes due to the change of the neighbor's community relationship.

After a certain number of update iterations, the community ownership of all nodes in the entire network has reached local stability.

Here, as a preferred solution, step 4. Dynamic maintenance process is also included.

The dynamic maintenance of the community structure mainly occurs in two situations. One is when a new node appears, and the other is that the logical neighbor relationship between the two nodes changes, that is, the two nodes that originally had no neighbor relationship dynamically become Two nodes that lost the neighbor relationship or were originally neighbors are no longer connected. In both ways, new neighbor relationships are discovered for existing nodes; when the logical relationship changes, the relevant nodes will find that new neighbors have appeared or neighbors have disappeared. At this time, the node publishes itself to all neighbors. The current tag list, initiates the tag update process.

The specific steps are shown in Figure 4:

Step 41. Each node checks whether the logical neighbor relationship changes;

Step 42. A new node appears: when the logical relationship changes, the relevant node will find that a new neighbor has appeared or a neighbor has disappeared. At this time, the node publishes its current label list to all neighbors, and initiates the label update process, that is, step 3.

Step 43. The logical neighbor relationship between two nodes has changed: that is, the two nodes that originally had no neighbor relationship dynamically become a neighbor relationship or the two nodes that were originally neighbors are no longer connected; when the logical relationship changes , the relevant nodes will find that new neighbors have appeared or some neighbors have disappeared. At this time, the node publishes its current label list to all neighbors, and initiates the label update process, that is, step 3.

The contribution of the inventive method is mainly reflected in the following aspects:

Neighbor information and label interaction: each node is only responsible for calculating its own label number, the topology information of the entire network does not need to be known by each node, each node only needs to know which neighbor nodes are, and can get its label The number list is enough, so the node should have the ability of label interaction, and can publish its own label to its neighbors, so that each node knows the label numbers owned by all its neighbors. The neighbor in the distributed community discovery method corresponds to the connected nodes in the traditional community discovery algorithm, and does not mean that the two nodes have a certain social relationship and can communicate with each other. Therefore, no special note is made, and the neighbors mentioned here refer to logical neighbors.

Label update synchronization: In the centralized label-based community discovery algorithm, there are two ways to calculate, synchronous and asynchronous, but no matter which way, the current calculation node can see the label numbers of all its neighbors at the same time information, because the centralized server has the topology information of the entire network. In the distributed community discovery process, the node can receive the label number of each neighbor because the node broadcasts its own label number to all neighbors. However, in a distributed system, nodes cannot receive label broadcasts issued by neighbors at the same time, nor can they determine when the currently received label broadcasts are issued by neighbors. Considering that when a node updates its own label, it only needs to collect the label information of the current iteration number of the neighbor node. Therefore, when the node exchanges label information, the parameter of iteration number is increased so that the node can distinguish whether the received neighbor label information is available. , the node considers the label number with the latest number of iterations to be a valid label, and each time the node updates its own label, the number of iterations carried in the broadcast label information is increased by 1.

Dynamic maintenance: Since there is no topology information of the entire network in the distributed system, when the network topology changes, such as new nodes joining or new logical relationships appearing, the newly added nodes or nodes with new logical relationships Actively publish new tag number information to all neighbor nodes, and the nodes near the topology change decide whether to update their own tag number information according to the policy, so as to dynamically maintain community information. The scope of community changes is mainly within the community and within the community that has overlapping nodes with the community, so it will not spread to the entire network.

Label dissemination control: If all labels are used for unlimited dissemination, after multiple label interactions, multiple large communities will be divided and repeated communities, thereby reducing the effect of community discovery. Here, the label is controlled by increasing the propagation factor The range of number propagation effectively improves the performance degradation of community division results after multiple iterations.

The workflow of the entire method model is as described above. During the tag update process, different update strategies can be used to achieve better community discovery results. Therefore, the method of the present invention can be used as a framework module to detect all tag-based community The algorithm is slightly modified and applied in different models, so that it is suitable for distributed community discovery algorithms.

Those skilled in the art will appreciate that the embodiments described here are to help readers understand the principles of the present invention, and it should be understood that the protection scope of the present invention is not limited to such specific statements and embodiments. Those skilled in the art can make various other specific modifications and combinations based on the technical revelations disclosed in the present invention without departing from the essence of the present invention, and these modifications and combinations are still within the protection scope of the present invention.

Claims (3)

1. one kind based on the mutual distributed Combo discovering method of label, specifically comprises the steps:

Step 1. arranges in the application scenarios information as can be known, specifically comprises: the initialization tag number of each node, and described tag number has uniqueness; The logic neighbours of each node;

Step 2. netinit process: all node is according to the tag number of local unique information initialization self in the network; The weight of this tag number is set to 1, and the propagation factor of tag number is initialized as 1; Local iterations is set is designated as 1, to the tag number of all neighbor node broadcasting oneself; The local neighbours' tag number tabulation of preserving of initialization, each the neighbours' label that arranges in neighbours' tag number tabulation of preservation is update mode not;

Step 3. tag update process: node receives the tag number broadcasting from neighbours, iterations in neighbours' tag number tabulation that contrast receives and the iterations of local respective neighbours list of labels of preserving, if the neighbor list iterations that the iterations in the neighbours' list of labels that receives is preserved greater than this locality, new neighbor list of labels more then, the corresponding lists state is set for upgrading, if be less than or equal to the local neighbor list iterations of preserving, then ignore this broadcasting packet; When the updating mark of all neighbours' tag numbers of nodes records when upgrading, upgrade local label number tabulation, update strategy is: with neighbours' tag number tabulation addition, the propagation factor of label is got propagation factor maximum in neighbours' same label and is deducted predefined propagation coefficient p, if the label propagation factor less than 0, is then deleted label; The label weight addition of same label number, all label weights of normalization, the deletion weight is less than the tag number of preliminary setting parameter 1/v, if all less than 1/v then keep the tag number of weight maximum, if a plurality of such tag numbers are arranged, then select at random the label of a weight limit, delete all the other labels, the tag number that keeps of normalization then, iterations adds 1, broadcast number tabulation of new local label to neighbours, all neighbours' of record list of labels updating mark is set to not upgrade; If after once upgrading, the tag number tabulation of node does not change, and shows that then the community structure that belongs under the node current state is stable.

2. according to claim 1 a kind of based on the mutual distributed Combo discovering method of label, it is characterized in that, also comprise the Dynamic Maintenance process, when occurring triggering the Dynamic Maintenance process when logic neighborhood between new node or two nodes changes, this moment, node was issued the list of labels of oneself to all neighbor nodes, initiated the tag update process.

3. according to claim 1 and 2 a kind ofly it is characterized in that based on the mutual distributed Combo discovering method of label, the described local unique information of step 2 is specially mac address or user name or node ID.

Images