CN107578136A - Overlapping Community Discovery Method Based on Random Walk and Seed Expansion - Google Patents

Abstract

The present invention relates to a method for discovering overlapping communities based on random walk and seed expansion, which uses random walk to select seed communities, calculates similarity and optimizes adaptive function community expansion to realize community discovery on large-scale social networks, including the following Steps: 1. Read the original data to obtain the network structure and node neighbor information; 2. Obtain the seed community set Seeds according to the node transition probability matrix, scoring matrix and the similarity between the node and the community; 3. Optimize according to the similarity between communities Seed community set Seeds ; 4. Extend the community according to the similarity between the seed and the community and the adaptive fitness function; 5. Process the free nodes in the network and merge similar communities according to the similarity between nodes and communities and the similarity between communities; 6. Output the network Overlapping community structures. This method can efficiently and accurately find overlapping communities.

Description

Overlapping Community Discovery Method Based on Random Walk and Seed Expansion

technical field

The invention relates to the technical field of discovering overlapping communities on social networks, in particular to a method for discovering overlapping communities based on random walk and seed expansion.

Background technique

There are many complex network structures in real life, such as social networks, scientist collaboration networks, literature citation networks, protein collaboration networks, and online social networks. The most critical feature of these complex networks is that they can be abstracted to be composed of many nodes and edges. Nodes represent individuals in the network, while edges represent connections between individuals, and edges can also be assigned weight values. Communities in complex networks usually require that the points within a community are closely connected, while the points between communities are sparsely connected. Community discovery is one of the key techniques for studying complex network structures. The purpose of community discovery is to efficiently and accurately discover these tight communities from complex network structures.

Community structure is an important structure in a complex network. How to efficiently and accurately mine the hidden structure and information of the community is still a difficult point. In recent years, many people have attracted many people to conduct in-depth research on it. At present, many global community discovery algorithms based on network structure division have been proposed, including hierarchical clustering algorithm, spectral method, clique-based method, edge clustering, label propagation, etc. Since the global community discovery algorithm requires an overall cognition of the entire network structure information, there are some defects in large-scale or incomplete complex networks, so there is a local community discovery algorithm based on seed expansion. The local community discovery algorithm based on seed expansion usually starts from the seed nodes in the network, and uses the local information of the community to continuously add nodes from the network to discover the community structure.

The existing local community discovery algorithm based on seed expansion has achieved some results in community discovery, but there are still several problems: first, the time and space complexity of the algorithm is relatively high, and there are deficiencies in dealing with large-scale networks; Secondly, the algorithm usually only selects nodes as seed nodes through a simple strategy, which affects the accuracy of community expansion mining; finally, in the community expansion stage, it fails to consider the closeness of nodes joining the community from multiple aspects, and the quality of the discovered community not tall.

Contents of the invention

The purpose of the present invention is to provide a method for discovering overlapping communities based on random walk and seed expansion, which can efficiently and accurately discover overlapping communities.

To achieve the above object, the technical solution of the present invention is: a method for discovering overlapping communities based on random walk and seed expansion, comprising the following steps:

Step 1: Read the original data to obtain the network structure and node neighbor information;

Step 2: Obtain the seed community set Seeds according to the transition probability matrix of the node, the scoring matrix and the similarity between the node and the community;

Step 3: Optimize the seed community set Seeds according to the similarity between communities;

Step 4: Extend the community according to the similarity between the seed and the community and the adaptive fitness function;

Step 5: Process free nodes in the network and merge similar communities according to the similarity between nodes and communities and between communities;

Step 6: Output network overlapping community structure.

Further, in step 2, according to the node transition probability matrix, scoring matrix and the similarity between the node and the community, the method of obtaining the seed community set Seeds is as follows:

Step 2.1: According to the network adjacency matrix A _uv and node degree k _v , get the transition probability matrix P _uv :

P _uv ＝A _uv /k _v (1)

The elements in P _uv represent the probability that node u walks randomly and reaches node v in one step;

Further obtain the transition probability matrix P ^t _uv after random walk t steps:

Step 2.2: According to the transition probability matrix P ^t _uv after walking for t steps, the scoring matrix B is obtained:

Among them, T represents the step threshold of random walk;

Each element in the scoring matrix B represents the score obtained by node u walking t steps to reach node v, represented by B(u,v), the closer the two nodes are connected, the higher the score between them;

Step 2.3: Sort B(u,v) in descending order, and take out the first l nodes with higher score values to form the initial seed list B-list;

Step 2.4: Calculate the node-community similarity NC_SIM(v,C _i ) between each node in the B-list as the initial seed community and its neighbor nodes. When the similarity is greater than the set threshold, the neighbor node is added to the seed community. Finally, the seed community collection Seeds is obtained;

Among them, v represents a node, is the degree of the edge associated with node v and community C _i , and k _v is the degree of node v; the larger NC_SIM(v,C _i ) is, the more likely node v belongs to community C _i .

Further, in step 3, the method of optimizing the seed community set Seeds according to the similarity between communities is as follows:

Step 3.1: traverse each seed community in the seed community set Seeds, and calculate the similarity CC_SIM(C _i , C _j ) between the communities;

Among them, |overlap(C _i , C _j )| is the number of nodes shared by community C _i and community C _j , |C _i | is the number of nodes in community C _i , |C _j | is the number of nodes in community C _j ; CC_SIM The larger (C _i , C _j ) indicates that the structure of the community C _i and the community C _j is more similar. When the set threshold ε is exceeded, the two communities will be merged into one community;

Step 3.2: If the similarity between communities is greater than the threshold ε, merge the two communities to obtain the optimized seed community set Seeds'.

Further, in step 4, the method of expanding the community according to the similarity between the seed and the community and the adaptive fitness function is as follows:

Step 4.1: first obtain the neighbor set NBSet of the seed community optimized in step 3, traverse the NBSet, and calculate the similarity NC_SIM(v,C _i ) between each neighbor node and the seed community;

Step 4.2: Take out the first l nodes with higher similarity to form the candidate node list C-list;

Step 4.3: Calculate the adaptive function fitness by adding the candidate nodes in the C-list to the community, and add the nodes that can increase the fitness to the community, otherwise set them as free nodes; the calculation formula of the adaptive function fitness is as follows:

in, with are the total value of the internal degree and external degree of the subgraph g, respectively, and the parameter α is a positive real number, which is used to control the size of the community found;

Step 4.4: Update NBSet, then repeat the above steps until NBSet is empty;

Step 4.5: Obtain the initial network overlapping community set C.

Further, in step 5, the method of processing free nodes in the network and merging similar communities according to the similarity between nodes and communities and between communities is as follows:

Step 5.1: Calculate the node-community similarity CC_SIM(C _i , C _j ) from free nodes to communities in the network, add free nodes to the community with the highest similarity, and update the overlapping community set C;

Step 5.2: Calculate the similarity CC_SIM(C _i , C _j ) between the communities in the overlapping community set C, merge the communities whose similarity is greater than the threshold ε, and obtain a new overlapping community set C'.

Further, in step 6, the method of outputting the overlapping community structure of the network is: according to a new overlapping community set C' obtained after optimization, each element in the set C' represents a community, and then output the generated overlapping community structure of the network.

The beneficial effect of the present invention is to combine the random walk strategy, similarity calculation and optimized adaptive function fitness, and apply it to the community discovery of a large-scale network, so that the overlapping community structure division in the network can be effectively obtained, and the network aggregation Class development in the direction of overlapping community discovery provides a useful complement.

Description of drawings

Fig. 1 is an implementation flow chart of the embodiment of the present invention.

detailed description

The present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

The present invention is based on the overlapping community discovery method of random walk and seed expansion, uses random walk to select seed communities, similarity calculation and optimized adaptive function community expansion, and realizes community discovery on large-scale social networks, as shown in Figure 1 , including the following steps:

Step 1: Read the original data to obtain the network structure and node neighbor information.

Step 2: Obtain the seed community set Seeds according to the transition probability matrix of the node, the scoring matrix and the similarity between the node and the community. The specific method is as follows:

Step 2.1: According to the network adjacency matrix A _uv and node degree k _v , get the transition probability matrix P _uv :

P _uv ＝A _uv /k _v (1)

The elements in P _uv represent the probability that node u walks randomly and reaches node v in one step;

Further obtain the transition probability matrix P ^t _uv after random walk t steps:

Step 2.2: According to the transition probability matrix P ^t _uv after walking for t steps, the scoring matrix B is obtained:

Among them, T represents the step threshold of random walk;

Each element in the scoring matrix B represents the score obtained by node u walking t steps to reach node v, represented by B(u,v), the closer the two nodes are connected, the higher the score between them;

Step 2.3: Sort B(u,v) in descending order, and take out the first l nodes with higher score values to form the initial seed list B-list;

Step 2.4: Calculate the node-community similarity NC_SIM(v,C _i ) between each node in the B-list as the initial seed community and its neighbor nodes. When the similarity is greater than the set threshold, the neighbor node is added to the seed community. Finally, the seed community collection Seeds is obtained;

Among them, v represents a node, is the degree of the edge associated with node v and community C _i , and k _v is the degree of node v; the larger NC_SIM(v,C _i ) is, the more likely node v belongs to community C _i .

Step 3: Optimize the seed community set Seeds according to the similarity between communities. The specific method is as follows:

Step 3.1: traverse each seed community in the seed community set Seeds, and calculate the similarity CC_SIM(C _i , C _j ) between the communities;

Among them, |overlap(C _i , C _j )| is the number of nodes shared by community C _i and community C _j , |C _i | is the number of nodes in community C _i , |C _j | is the number of nodes in community C _j ; CC_SIM The larger (C _i , C _j ) indicates that the structure of the community C _i and the community C _j is more similar. When the set threshold ε is exceeded, the two communities will be merged into one community;

Step 3.2: If the similarity between communities is greater than the threshold ε, merge the two communities to obtain the optimized seed community set Seeds'. In this embodiment, the threshold ε is 0.5.

Step 4: Expand the community according to the similarity between the seed and the community and the adaptive fitness function. The specific method is:

Step 4.1: First obtain the neighbor set NBSet of the seed community optimized in step 3, traverse the NBSet, and calculate the similarity NC_SIM(v,C _i ) between each neighbor node and the seed community, and the calculation formula is shown in formula (4) ;

Step 4.2: Take out the first l nodes with higher similarity to form the candidate node list C-list;

Step 4.3: Calculate the adaptive function fitness by adding the candidate nodes in the C-list to the community, and add the nodes that can increase the fitness to the community, otherwise set them as free nodes; the calculation formula of the adaptive function fitness is as follows:

in, with are the total value of the internal degree and external degree of the subgraph g, respectively, and the parameter α is a positive real number, which is used to control the size of the community found;

Step 4.4: Update NBSet, then repeat the above steps until NBSet is empty;

Step 4.5: Obtain the initial network overlapping community set C.

Step 5: Process free nodes in the network and merge similar communities according to the node-community similarity and inter-community similarity. The specific method is:

Step 5.1: Calculate the node-community similarity CC_SIM(C _i , C _j ) from free nodes to communities in the network, add free nodes to the community with the highest similarity, and update the overlapping community set C;

Step 5.2: Calculate the similarity CC_SIM(C _i , C _j ) between the communities in the overlapping community set C, merge the communities whose similarity is greater than the threshold ε, and obtain a new overlapping community set C'.

Step 6: Output network overlapping community structure. The specific method is: according to the optimization, a new overlapping community set C' is obtained, each element in the set C' represents a community, and then the generated network overlapping community structure is output.

The above are the preferred embodiments of the present invention, and all changes made according to the technical solution of the present invention, when the functional effect produced does not exceed the scope of the technical solution of the present invention, all belong to the protection scope of the present invention.

Claims (6)

1. A method for discovering overlapping communities based on random walk and seed expansion, characterized in that, comprising the following steps: Step 1: Read the original data to obtain the network structure and node neighbor information; Step 2: Obtain the seed community set Seeds according to the transition probability matrix of the node, the scoring matrix and the similarity between the node and the community; Step 3: Optimize the seed community set Seeds according to the similarity between communities; Step 4: Extend the community according to the similarity between the seed and the community and the adaptive fitness function; Step 5: Process free nodes in the network and merge similar communities according to the similarity between nodes and communities and between communities; Step 6: Output network overlapping community structure. 2. The overlapping community discovery method based on random walk and seed expansion according to claim 1, characterized in that in step 2, according to the transition probability matrix, scoring matrix and similarity between nodes and communities of nodes, the seeds are obtained The method of collecting Seeds in the community is as follows: Step 2.1: According to the network adjacency matrix A _uv and node degree k _v , get the transition probability matrix P _uv : P _uv ＝A _uv /k _v (1) The elements in P _uv represent the probability that node u walks randomly and reaches node v in one step; Further obtain the transition probability matrix P ^t _uv after random walk t steps: Step 2.2: According to the transition probability matrix P ^t _uv after walking for t steps, the scoring matrix B is obtained: <mrow><mi>B</mi><mo>=</mo><munderover><mo>&amp;Sigma;</mo><mrow><mi>t</mi><mo>=</mo><mn>1</mn></mrow><mi>T</mi></munderover><msubsup><mi>P</mi><mrow><mi>u</mi><mi>v</mi></mrow><mi>t</mi></msubsup><mo>-</mo><mo>-</mo><mo>-</mo><mrow><mo>(</mo><mn>3</mn><mo>)</mo></mrow></mrow> Among them, T represents the step threshold of random walk; Each element in the scoring matrix B represents the score obtained by node u walking t steps to reach node v, represented by B(u,v), the closer the two nodes are connected, the higher the score between them; Step 2.3: Sort B(u,v) in descending order, and take out the first l nodes with higher score values to form the initial seed list B-list; Step 2.4: Calculate the node-community similarity NC_SIM(v,C _i ) between each node in the B-list as the initial seed community and its neighbor nodes. When the similarity is greater than the set threshold, the neighbor node is added to the seed community. Finally, the seed community collection Seeds is obtained; <mrow><mi>N</mi><mi>C</mi><mo>_</mo><mi>S</mi><mi>I</mi><mi>M</mi>><mrow><mo>(</mo><mi>v</mi><mo>,</mo><msub><mi>C</mi><mi>i</mi></msub><mo>)</mo></mrow><mo>=</mo><mfrac><msubsup><mi>k</mi><mi>v</mi><msub><mi>C</mi><mi>i</mi></msub></msubsup><msub><mi>k</mi><mi>v</mi></msub></mfrac><mo>-</mo><mo>-</mo><mo>-</mo><mrow><mo>(</mo><mn>4</mn><mo>)</mo></mrow></mrow> Among them, v represents a node, is the degree of the edge associated with node v and community C _i , and k _v is the degree of node v; the larger NC_SIM(v,C _i ) is, the more likely node v belongs to community C _i . 3. The overlapping community discovery method based on random walk and seed expansion according to claim 2, characterized in that, in step 3, the method of optimizing the seed community set Seeds according to the similarity between communities is as follows: Step 3.1: traverse each seed community in the seed community set Seeds, and calculate the similarity CC_SIM(C _i , C _j ) between the communities; <mrow><mi>C</mi><mi>C</mi><mo>_</mo><mi>S</mi><mi>I</mi><mi>M</mi>><mrow><mo>(</mo><msub><mi>C</mi><mi>i</mi></msub><mo>,</mo><msub><mi>C</mi><mi>j</mi></msub><mo>)</mo></mrow><mo>=</mo><mfrac><mrow><mo>|</mo><mi>o</mi><mi>v</mi><mi>e</mi><mi>r</mi><mi>l</mi><mi>a</mi><mi>p</mi><mrow><mo>(</mo><msub><mi>C</mi><mi>i</mi></msub><mo>,</mo><msub><mi>C</mi><mi>j</mi></msub><mo>)</mo></mrow><mo>|</mo></mrow><mrow><mi>min</mi><mrow><mo>(</mo><mo>|</mo><msub><mi>C</mi><mi>i</mi></msub><mo>|</mo><mo>,</mo><mo>|</mo><msub><mi>C</mi><mi>j</mi></msub><mo>|</mo><mo>)</mo></mrow></mrow></mfrac><mo>-</mo><mo>-</mo><mo>-</mo><mrow><mo>(</mo><mn>5</mn><mo>)</mo></mrow></mrow> Among them, |overlap(C _i , C _j )| is the number of nodes shared by community C _i and community C _j , |C _i | is the number of nodes in community C _i , |C _j | is the number of nodes in community C _j ; CC_SIM The larger (C _i , C _j ) indicates that the structure of the community C _i and the community C _j is more similar. When the set threshold ε is exceeded, the two communities will be merged into one community; Step 3.2: If the similarity between communities is greater than the threshold ε, merge the two communities to obtain the optimized seed community set Seeds'. 4. The overlapping community discovery method based on random walk and seed expansion according to claim 3, characterized in that, in step 4, the method of expanding community according to seed and community similarity and adaptive fitness function is as follows: Step 4.1: first obtain the neighbor set NBSet of the seed community optimized in step 3, traverse the NBSet, and calculate the similarity NC_SIM(v,C _i ) between each neighbor node and the seed community; Step 4.2: Take out the first l nodes with higher similarity to form the candidate node list C-list; Step 4.3: Calculate the adaptive function fitness by adding the candidate nodes in the C-list to the community, and add the nodes that can increase the fitness to the community, otherwise set them as free nodes; the calculation formula of the adaptive function fitness is as follows: <mrow><msub><mi>f</mi><mi>g</mi></msub><mo>=</mo><mfrac><msubsup><mi>k</mi><mrow><mi>i</mi><mi>n</mi></mrow><mi>g</mi></msubsup><msup><mrow><mo>(</mo><msubsup><mi>k</mi><mrow><mi>i</mi><mi>n</mi></mrow><mi>g</mi></msubsup><mo>+</mo><msubsup><mi>k</mi><mrow><mi>o</mi><mi>u</mi><mi>t</mi></mrow><mi>g</mi></msubsup><mo>)</mo></mrow><mi>&amp;alpha;</mi></msup></mfrac><mo>-</mo><mo>-</mo><mo>-</mo><mrow><mo>(</mo><mn>6</mn><mo>)</mo></mrow></mrow> in, with are the total value of the internal degree and external degree of the subgraph g, respectively, and the parameter α is a positive real number, which is used to control the size of the community found; Step 4.4: Update NBSet, then repeat the above steps until NBSet is empty; Step 4.5: Obtain the initial network overlapping community set C. 5. The overlapping community discovery method based on random walk and seed expansion according to claim 4, wherein in step 5, the free nodes in the network are processed and merged according to the similarity between nodes and communities and the similarity between communities The methods for similar communities are as follows: Step 5.1: Calculate the node-community similarity CC_SIM(C _i , C _j ) from free nodes to communities in the network, add free nodes to the community with the highest similarity, and update the overlapping community set C; Step 5.2: Calculate the similarity CC_SIM(C _i , C _j ) between the communities in the overlapping community set C, merge the communities whose similarity is greater than the threshold ε, and obtain a new overlapping community set C'. 6. The method for discovering overlapping communities based on random walk and seed expansion according to claim 1, characterized in that in step 6, the method of outputting the network overlapping community structure is: according to the new overlapping community set C obtained after optimization ', each element in the set C' represents a community, and then output the generated network overlapping community structure.