CN113052408B

CN113052408B - Method and device for community aggregation

Info

Publication number: CN113052408B
Application number: CN201911260423.6A
Authority: CN
Inventors: 王凯; 王辉; 万骏泓
Original assignee: Hangzhou Hikvision Digital Technology Co Ltd
Current assignee: Hangzhou Hikvision Digital Technology Co Ltd
Priority date: 2019-12-10
Filing date: 2019-12-10
Publication date: 2024-02-23
Anticipated expiration: 2039-12-10
Also published as: CN113052408A

Abstract

The application relates to a method and a device for community aggregation, and belongs to the field of monitoring. The method comprises the following steps: acquiring a first community set; acquiring a module degree increasing value of any two neighbor nodes of a first node, and moving the first node from a first community to a community where one of the two neighbor nodes is located according to the module degree increasing value of the two neighbor nodes in a first community set to obtain a second community set, wherein the first community is the community where the first node is located; acquiring a module degree increasing value of each neighbor node of a second node, and moving the second node from a second community to a community where the neighbor node corresponding to the maximum module degree increasing value is located in the second community set when the maximum module degree increasing value in the module degree increasing value corresponding to each neighbor node exceeds a preset threshold value to obtain a third community set, wherein the second community is the community where the second node is located. The method and the device can reduce the time consumption for identifying communities.

Description

Method and device for community aggregation

Technical Field

The present application relates to the field of monitoring, and in particular, to a method and apparatus for community aggregation.

Background

Along with the development of information technology, a large number of information features of users are stored in an information system, and certain relevance exists between the users, so that the features of the users have multiple dimensions and multiple relevance. The information system may store information characteristics of a large number of users in a graph, where each user is a node, and each node is connected to its surrounding nodes by edges to form a network.

To help people more effectively understand the structural features of the network, community identification techniques are currently employed to identify communities from the network, which may be clusters of at least one node, with nodes within the same community having the same interest, and then based on the identified communities for downstream applications.

At present, a random neighbor LOUVAIN algorithm can be used for identifying communities from the graph, but the random neighbor LOUVAIN algorithm has high complexity, and when the graph comprises a large number of nodes, the time for identifying communities from the graph is high.

Disclosure of Invention

The embodiment of the application provides a method and a device for community aggregation, which are used for reducing time consumption for identifying communities. The technical scheme is as follows:

in one aspect, the present application provides a method of community aggregation, the method comprising:

Obtaining a first community set, wherein the first community set comprises a plurality of communities, each community comprises one node in a graph, and the graph is an undirected graph comprising a plurality of nodes;

acquiring a modularity increasing value of any two neighbor nodes of a first node, wherein the first node is any node in the graph; moving the first node from a first community to a community where one of the two neighbor nodes is located according to the modularity increment value of the two neighbor nodes in the first community set to obtain a second community set, wherein the first community is the community where the first node is located;

acquiring a modularity increasing value of each neighbor node of a second node, wherein the second node is any node in the graph; and when the maximum modularity increasing value in the modularity increasing values corresponding to each neighbor node exceeds a preset threshold, moving the second node from a second community to the community where the neighbor node corresponding to the maximum modularity increasing value is located in the second community set to obtain a third community set, wherein the second community is the community where the second node is located.

As an example, the obtaining the module degree increment value of any two neighboring nodes of the first node includes:

Moving a first node from a first community to communities where first neighbor nodes are located and obtaining first module degree added values of all communities at present, wherein the first module degree added values are module degree added values of the first neighbor nodes, and the first neighbor nodes are any neighbor node of the first node;

moving the first node from a community where a first neighbor node is located to a community where a second neighbor node is located and obtaining second module degree added values of all communities at present, wherein the second module degree added values are module degree added values of the second neighbor node, and the second neighbor node is another neighbor node of the first node;

as an example, the adding the first node to the community where one of the two neighboring nodes is located according to the module value of the two neighboring nodes includes:

selecting a maximum modular incremental value from the first modular incremental value and the second modular incremental value;

and when the maximum modularity increasing value is greater than 0, moving the first node from the community where the second neighbor node is located to the community where the neighbor node corresponding to the maximum modularity increasing value is located.

As an example, after the moving the first node from the first community to the community where one of the two neighboring nodes is located according to the module value of the two neighboring nodes, the method further includes:

after the module block increment values of two neighboring nodes of each node in the graph are obtained, increasing first community identification times, selecting one node from other nodes in the graph as a first node when the first community identification times do not reach a first preset time threshold, and executing the operation of obtaining the module increment values of any two neighboring nodes of the first node; and when the first community identification times reach a first preset times threshold, executing the module degree increasing value of each neighbor node of the second node after moving the first node to the community where one neighbor node of the two neighbor nodes is located.

As an example, the obtaining the module value of each neighboring node of the second node includes:

and moving the second node to the community where one neighbor node of the second node is located, acquiring the module degree increasing value of all communities currently, and determining the module degree increasing value as the module degree increasing value of the one neighbor node.

As an example, the method further comprises:

and when the maximum value in the module degree increment value corresponding to each neighbor node does not exceed a preset threshold, increasing second community identification times, and when the second community identification times do not reach the second preset times threshold, determining each identified community as one node in the graph, and executing the operation of determining each node in the graph as one community.

In another aspect, the present application provides an apparatus for community aggregation, the apparatus comprising:

an acquisition module, configured to acquire a first community set, where the first community set includes a plurality of communities, each community includes a node in a graph, and the graph is an undirected graph including a plurality of nodes;

the first mobile module is used for acquiring the module degree increment value of any two neighbor nodes of a first node, wherein the first node is any node in the graph; moving the first node from a first community to a community where one of the two neighbor nodes is located according to the modularity increment value of the two neighbor nodes in the first community set to obtain a second community set, wherein the first community is the community where the first node is located;

The second mobile module is used for acquiring the module degree increment value of each neighbor node of a second node, and the second node is any node in the graph; and when the maximum modularity increasing value in the modularity increasing values corresponding to each neighbor node exceeds a preset threshold, moving the second node from a second community to the community where the neighbor node corresponding to the maximum modularity increasing value is located in the second community set to obtain a third community set, wherein the second community is the community where the second node is located.

As an example, the first mobile module includes:

the mobile terminal comprises a first mobile unit, a second mobile unit and a first neighbor node, wherein the first mobile unit is used for moving a first node from a first community to the community where the first neighbor node is located and acquiring a first module degree added value of all communities at present, the first module degree added value is the module degree added value of the first neighbor node, and the first neighbor node is any neighbor node of the first node;

the second mobile unit is used for moving the first node from a community where a first neighbor node is located to a community where a second neighbor node is located and obtaining second module degree added values of all communities at present, wherein the second module degree added values are module degree added values of the second neighbor node, and the second neighbor node is another neighbor node of the first node;

As an example, the first mobile module further comprises:

the selecting unit is used for selecting the maximum module degree increasing value from the first module degree increasing value and the second module degree increasing value;

and the third mobile unit is used for moving the first node from the community where the second neighbor node is located to the community where the neighbor node corresponding to the maximum modularity increasing value is located when the maximum modularity increasing value is greater than 0.

As an example, the apparatus further comprises:

the selection module is used for increasing first community identification times after obtaining the module block increment values of two adjacent nodes of each node in the graph, and selecting one node from other nodes in the graph as a first node when the first community identification times do not reach a first preset time threshold value, and executing the operation of obtaining the module increment value of any two adjacent nodes of the first node; and when the first community identification times reach a first preset times threshold, executing the module degree increasing value of each neighbor node of the second node after moving the first node to the community where one neighbor node of the two neighbor nodes is located.

As an example, the second mobile module is configured to move a second node to a community where one neighboring node of the second node is located, obtain a module degree added value of all communities currently, and determine the module degree added value as the module degree added value of the one neighboring node.

As an example, the determining module is further configured to:

The technical scheme provided by the embodiment of the application can comprise the following beneficial effects:

the method comprises the steps of obtaining a module degree increasing value of any two neighbor nodes in a first community set, and moving the node to a community where one of the two neighbor nodes is located according to the module degree increasing value of the two neighbor nodes in the first community set to obtain a second community set. The module degree increasing values of the two neighbor nodes are obtained, so that the number of the nodes participating in operation is small, and a large number of nodes in the first community set can be clustered into communities rapidly. And then, acquiring a modularity increasing value of each neighbor node of the nodes in the second community set, and moving the second node to the community where the neighbor node corresponding to the maximum modularity increasing value is located, so that the graph can be converged rapidly, the accuracy of community identification is improved, and the time consumption of community identification is reduced.

It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the application.

Drawings

The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate embodiments consistent with the application and together with the description, serve to explain the principles of the application.

FIG. 1 is a schematic view of a structure of a diagram provided in an embodiment of the present application;

FIG. 2 is a flow chart of a method for community aggregation provided by an embodiment of the present application;

FIG. 3 is a flow chart of another method for community aggregation provided by an embodiment of the present application;

FIG. 4 is a schematic structural view of another diagram provided by an embodiment of the present application;

FIG. 5 is a schematic diagram of a device structure for community aggregation according to an embodiment of the present application;

fig. 6 is a schematic diagram of a terminal structure according to an embodiment of the present application.

Specific embodiments thereof have been shown by way of example in the drawings and will herein be described in more detail. These drawings and the written description are not intended to limit the scope of the inventive concepts in any way, but to illustrate the concepts of the present application to those skilled in the art by reference to specific embodiments.

Detailed Description

Reference will now be made in detail to exemplary embodiments, examples of which are illustrated in the accompanying drawings. When the following description refers to the accompanying drawings, the same numbers in different drawings refer to the same or similar elements, unless otherwise indicated. The implementations described in the following exemplary examples are not representative of all implementations consistent with the present application. Rather, they are merely examples of apparatus and methods consistent with some aspects of the present application as detailed in the accompanying claims.

Referring to the graph shown in fig. 1, the graph may be an undirected graph including a plurality of nodes, for each node in the graph, the node may be connected to its neighbors using edges. Each node in the graph may be a user, and an edge connection exists between the node and its neighboring nodes, which indicates that there is some relationship between the two users, for example, the two users may be friends with each other. In the application, communities can be identified in the graph through any embodiment, and the communities are node clusters obtained by clustering nodes with the same interests.

Referring to fig. 2, an embodiment of the present application provides a method for community aggregation, the method including:

step 201: a first community set is obtained, the first community set comprising a plurality of communities, each community comprising a node in a graph.

In this step, each node in a graph, which is an undirected graph including a plurality of nodes, is determined as one community and constitutes a first community set, and the number of nodes in the graph is equal to the determined number of communities.

Step 202: acquiring a modularity increasing value of any two neighbor nodes of a first node, wherein the first node is any node in a first community set; and moving the first node from the first community to the community where one of the two neighbor nodes is located according to the modular increment value of the two neighbor nodes in the first community set to obtain a second community set, wherein the first community is the community where the first node is located.

The method is an implementation process of a binary random neighbor LOUAIN iterative algorithm. The algorithm only acquires the module degree increment values of two neighbor nodes of the first node, and the number of the neighbor nodes needing to participate in the operation is small, so that the algorithm has low computational complexity. Therefore, in the step, firstly, the iterative algorithm is used for carrying out community identification on the nodes in the first community set, so that the first community set can be converged rapidly, a large number of nodes in the first community set are clustered into communities, and a second community set is obtained. However, only the first community set can be clustered in a coarse frame in this step, so that after performing the operation of step 202 at least once on each node in the first community set, a second community set is obtained, and then the operation of step 203 can be performed on the second community set.

Step 203: acquiring a modularity increasing value of each neighbor node of a second node, wherein the second node is any node in the second community set; when the maximum modularity increasing value in the modularity increasing values corresponding to each neighbor node exceeds a preset threshold, moving the second node from the second community to the community where the neighbor node corresponding to the maximum modularity increasing value is located in the second community set, and obtaining a third community set, wherein the second community is the community where the second node is located.

The method is an implementation process of a random neighbor LOUAIN iterative algorithm. The algorithm acquires the modular increment value of each neighbor node of the second node, and the second node possibly has more neighbor nodes in the second community set, so that the number of the neighbor nodes needing to participate in the operation is more, the calculation complexity of the algorithm is higher, and the clustering effect of the second community set is better. However, in this step, a large number of nodes in the second community set are clustered into communities, and then the second community set is further clustered in a refined manner by using this step, so that the second community set can be quickly used for convergence, and the effect of community clustering is ensured.

The execution main body of the method can be a terminal or a server, and the terminal can be a mobile phone, a notebook computer or a desktop computer.

In the embodiment of the application, for any node in the first community set, namely the first node, the module degree increasing value of any two neighbor nodes of the first node is obtained, the first node is moved to the community where one neighbor node in the two neighbor nodes is located according to the module degree increasing value of the two neighbor nodes, and the number of nodes participating in operation is small because the community is clustered between the first node and the two neighbor nodes, so that a large number of nodes in the first community set can be clustered into communities rapidly to obtain the second community set. Then, for each node in the second community set, namely the second node, the module degree increasing value of each neighbor node of the second node is obtained, the second node is moved to the community where the neighbor node corresponding to the maximum module degree increasing value is located, and because a large number of nodes are clustered into the second community set of the community, the community is further clustered between the second node and each neighbor node, so that the second community set can be quickly converged, the accuracy of community identification is improved, and the time consumption of community identification is reduced.

Referring to fig. 3, an embodiment of the present application provides a method for community aggregation, including:

Step 301: a first community set is obtained, the first community set comprising a plurality of communities, each community comprising a node in a graph.

In this step, each node in the graph is determined to be a community, and a first community set is obtained. The graph is an undirected graph including a plurality of nodes, the number of nodes in the graph being equal to the number of communities in the first community set.

Each node in the graph has an ID number of the node, for each node, the ID number of the node can be determined as the number of the community where the node is located, and the ID number of the node and the number of the community where the node is located are correspondingly stored in a corresponding relation table, so that each node in the graph is determined as a community.

For example, referring to the graph shown in fig. 1, the graph includes 15 nodes, and 15 communities are formed after each node in the graph is determined to be one community. The 15 nodes are nodes 1, 2, 3, … … and 15 respectively, and the ID numbers of the nodes 1, 2, 3, … … and 15 are 1, 2, 3, … … and 15 respectively. The ID number "1" of the node 1 is determined as the number of the community in which the node 1 is located, the ID number "2" of the node 2 is determined as the number of the community in which the node 1 is located, the ID number "3" of the node 3 is determined as the number of the community in which the node 3 is located, … …, and the ID number "15" of the node 15 is determined as the number of the community in which the node 15 is located. Wherein the first community set comprises communities numbered 1, 2, 3, … …, 15, i.e. initially the first community set comprises 15 communities, as shown in fig. 1.

After each node in the graph is determined to be a community, a first community set is obtained, module degree values corresponding to all communities are calculated based on all communities currently included in the first community set, and the module degree values are recorded. The modularity value is a measure of the degree of clustering of communities, and is used to represent the reasonable degree of all communities currently identified. The higher the modularity value, the higher the rationality indicating all communities currently identified, and conversely the lower the rationality indicating all communities currently identified.

For example, each node in the graph shown in fig. 1 is determined as one community, and then 15 communities are obtained, which are communities 1, 2, 3, … …, and 15 in the first community set, respectively, and a module value v1 corresponding to the 15 communities is calculated based on communities 1, 2, 3, … …, and 15, and the module value v1 is recorded.

Step 302: and obtaining the module degree increment value of any two neighbor nodes of the first node, wherein the first node is any node in the graph.

In this step, this can be achieved by the operations 3021 to 3023 as follows. The operations of 3021 to 3023 may be respectively:

3021: one node is selected from the first community set as a first node, and two neighbor nodes are randomly selected from neighbor nodes of the first node, and are respectively called a first neighbor node and a second neighbor node for convenience of explanation.

After one node is selected from the first community set to serve as a first node, each node connected with edges existing between the first nodes is obtained from the first community set to serve as a neighbor node of the first node, and the first neighbor node and the second neighbor node are randomly selected from the neighbor nodes of the first node.

For example, node 1 is selected from the first community set shown in fig. 1 as a first node, nodes 2, 4, 7 connected with edges between the first nodes are acquired from the first community set as neighbor nodes of the first node, and two neighbor nodes are randomly selected from the neighbor nodes 2, 4, 7 of the first node. Assuming that the neighbor nodes 2 and 4 are selected, the neighbor node 2 is taken as a first neighbor node, and the neighbor node 4 is taken as a second neighbor node.

3022: and moving the first node from the first community to the community where the first neighbor node is located, and acquiring a first module degree added value of all the communities at present, wherein the first module degree added value is the module degree added value of the first neighbor node, and the first community is the community where the first node is located.

In the step, the number of the first community corresponding to the first node is modified to be the number of the community where the first neighbor node is located in the corresponding relation table, the first node is moved from the first community to the community where the first neighbor node is located, the module degree value corresponding to all communities at present is calculated based on all communities at present, the difference value between the module degree value and the recorded module degree value is calculated, and the difference value is used as the module degree increment value of the first neighbor node.

For example, in the first community set shown in fig. 1, the number of the first community corresponding to the first node 1 is modified to be the number 2 of the community 2 where the first neighbor node 2 is located, so as to implement the movement of the first node 1 from the community 1 to the community 2. At this time, all communities currently include 14 communities, namely communities 2, 3, 4, … … and 15, wherein the community 2 includes a first node 1 and a node 2, and each other community includes a node. And calculating a module degree value v2 corresponding to the current 14 communities based on the current 14 communities, calculating a difference value Deltaw1=v2-v1 between the module degree value v2 and the recorded module degree value v1, and taking the difference value Deltaw 1 as a module degree increment value of the first neighbor node 2, namely the first module degree increment value is Deltaw 1.

3023: and moving the first node from the community where the first neighbor node is located to the community where the second neighbor node is located, and acquiring second module degree added values of all the communities currently, wherein the second module degree added values are module degree added values of the second neighbor node.

In the step, the number of the community corresponding to the first node is modified to the number of the community where the second neighbor node is located in the corresponding relation table, the first node is moved to the community where the second neighbor node is located, the module degree value corresponding to all the communities at present is calculated based on all the communities at present, the difference value between the module degree value and the recorded module degree value is calculated, and the difference value is used as the module degree increasing value of the second neighbor node.

For example, in the first community set shown in fig. 1, the number of the community corresponding to the first node 1 is modified to be the number 4 of the community 4 where the second neighbor node 4 is located, so that the first node 1 is moved to the community 4. At this time, all communities in the current first community set include 14 communities, namely communities 2, 3, 4, … … and 15, wherein the community 4 includes a first node 1 and a node 4, and each other community includes a node. And calculating a module degree value v3 corresponding to the current 14 communities based on the current 14 communities, calculating a difference value Deltaw2=v3-v1 between the module degree value v3 and the recorded module degree value v1, and taking the difference value Deltaw 2 as a module degree increment value of the second neighbor node 4, namely, the second module degree increment value is Deltaw 2.

Step 303: and adding the first node to the community where one of the two neighbor nodes is located according to the module degree increasing value of the two neighbor nodes.

In the step, the maximum module degree increasing value is selected from the first module degree increasing value and the second module degree increasing value; when the maximum modularity increasing value is greater than 0, moving the first node from the community where the second neighbor node is located to the community where the neighbor node corresponding to the maximum modularity increasing value is located; and when the maximum modularity increment value is smaller than or equal to 0, the first node is stayed in the first community, namely the first node is moved into the first community from the community where the second neighbor node is located.

When the maximum modularity increasing value is greater than 0, the relevance between the first node and the node in the community where the neighbor node corresponding to the maximum modularity increasing value is located is higher, and the reasonable degree of community division can be increased after the first node is added to the community where the neighbor node corresponding to the maximum modularity increasing value is located.

When the maximum modularity increment value is smaller than or equal to 0, the relevance between the first node and the nodes in the communities where the first neighbor node is located is lower, and the relevance between the first node and the nodes in the communities where the second neighbor node is located is also lower, so that the first node does not need to be moved to the communities where the first neighbor node is located and the communities where the second neighbor node is located.

When the maximum module degree increment value is larger than 0, the recorded module degree value and the maximum module degree increment value are accumulated, and the recorded module degree value is updated to be an accumulated value obtained by accumulation. Or determining the neighbor node corresponding to the maximum modularity increment value, and updating the recorded modularity value to the modularity value corresponding to the neighbor node.

For example, assuming that the first module degree increment value is Δw1 greater than the second module degree increment value is Δw2, and the first module degree increment value is Δw1 greater than 0, the first node 1 is moved to the community 2 where the neighbor node 2 corresponding to the maximum module degree increment value is located. Accumulating the recorded module degree value v1 and the first module degree increasing value delta w1 to obtain an accumulated value v2, and updating the recorded module degree value v1 into the accumulated value v2.

If there is an unselected node in the first community set, one node is randomly selected from the unselected nodes as the first node, and then the operations of steps 302 to 303 described above are repeatedly performed. If there are no unselected nodes in the first community set, step 304 is performed.

For example, for the nodes not selected in the graph shown in fig. 1 being nodes 2, 3, … …, 15, one node is randomly selected from the nodes 2, 3, … …, 15, assuming that the node 2 is selected as the first node, then the operations of steps 302 to 303 described above are repeatedly performed until the operations of steps 302 to 303 described above are performed for each of the nodes 1, 2, 3, … …, 15, the operations of the following step 304 are not started to be performed.

Step 304: increasing the first community identification times, and when the first community identification times do not reach a first preset time threshold, randomly selecting one node from nodes included in the first community set as a first node, and executing step 302; when the first community identification number reaches the first preset number threshold, the first community set at this time is used as the second community set, and step 305 is executed.

In this embodiment, the number of times of repeatedly executing the steps 302 to 303 on the nodes in the first community set may be set to reach the first preset number of times threshold, and the following step 305 may be started. In the above steps, only the module degree increment value of any two neighboring nodes of the first node needs to be obtained, and the obtained module degree increment value is less, so that the steps 302 and 303 can be executed quickly, and a plurality of communities can be clustered quickly from a large number of nodes included in the first community set.

The first preset number of times threshold may be a value of 1, 2, or 3, etc.

For example, suppose that the operations of steps 302 to 303 described above are performed a first predetermined number of times on nodes in the first community set shown in fig. 1, and communities in fig. 1 are clustered into communities 2, 4, 5, 8, and 10, where the first community set serves as a second community set, and the second community set includes communities 2, 4, 5, 8, and 10. Assuming that the nodes 1, 2 and 3 are included in the community 2, the community 4 includes the nodes 4, 7 and 9, the community 5 includes the nodes 5 and 11, the community 8 includes the nodes 6 and 12, and the community 10 includes the nodes 10, 13, 14 and 15.

Step 305: and acquiring a modularity increment value of each neighbor node of the second node in the second community set, wherein the second node is any node in the second community set.

In this step, it can be realized by the operations of 3051 to 3052 as follows. The operations of 3051-3052 can be respectively:

3051: and selecting one node from the second community set as a second node, and randomly selecting one neighbor node from neighbor nodes of the second node.

After one node is selected from the second community set to serve as a second node, each node connected with edges between the second nodes is obtained from the second community set to serve as a neighbor node of the second node, and one neighbor node is randomly selected from the neighbor nodes of the second node.

For example, node 1 is selected from the second community set as the second node, nodes 2, 4 and 7 connected with edges between the second nodes are obtained from the second community set as neighbor nodes of the second node, and one neighbor node is randomly selected from the neighbor nodes 2, 4 and 7 of the second node. Suppose that neighbor node 4 is selected.

3052: and moving the second node from the second community to the community where the neighbor node is located, acquiring the module degree added value of all the communities currently, determining the module degree added value as the module degree added value of the neighbor node, and determining the second community as the community where the second node is located.

In the step, the number of the community corresponding to the second node is modified to be the number of the community where the neighbor node is located in the corresponding relation table, so that the second node is moved to the community where the neighbor node is located, the module degree value corresponding to all communities at present is calculated based on all communities at present, the difference value between the module degree value and the recorded module degree value is calculated, and the difference value is used as the module degree increasing value of the neighbor node.

If the neighbor node of the second node still has the neighbor node which is not selected, then randomly selecting a node from the neighbor nodes which are not selected, and then executing the step until all the neighbor nodes of the second node are selected.

For example, in the second community set, the number of the community corresponding to the second node 1 is modified to be the number 4 of the community 4 where the neighboring node 4 is located, so as to realize that the second node 1 is moved into the community 4. At this time, all communities currently include 5 communities, namely communities 2, 4, 5, 8 and 10, respectively, wherein community 2 includes nodes 2 and 3, community 4 includes nodes 4, 7 and 9, and each of communities 5, 8 and 10 has a constant node, namely community 5 includes nodes 5 and 11, community 8 includes nodes 6 and 12, and community 10 includes nodes 10, 13, 14 and 15. And calculating a difference value Deltaw 5 = v2-v between the module degree value v4 and the recorded module degree value v based on the module degree value v4 corresponding to the current 5 communities and taking the difference value Deltaw 5 as a module degree increment value of the neighbor node 4.

Selecting a neighbor node 2 from the neighbor nodes 2, 4 and 7 of the second node, repeatedly executing 3052 to obtain a module degree increment value Deltaw 6 of the neighbor node 2, selecting a neighbor node 7 from the neighbor nodes 2, 4 and 7 of the second node, and repeatedly executing 3052 to obtain a module degree increment value Deltaw 7 of the neighbor node 7.

Step 306: and when the maximum modularity increasing value in the modularity increasing values corresponding to each neighbor node exceeds a preset threshold, moving the second node to the community where the neighbor node corresponding to the maximum modularity increasing value is located, and obtaining a third community set.

When the maximum modularity increasing value exceeds a preset threshold, the relevance between the second node and the node in the community where the neighbor node corresponding to the maximum modularity increasing value is located is higher, and the reasonable degree of community clustering can be increased after the second node is moved to the community where the neighbor node corresponding to the maximum modularity increasing value is located.

When the maximum modularity increase value does not exceed the preset threshold, it indicates that the association between the second node and the nodes in the community where each of its neighboring nodes is located is low, so that the second node does not need to be added to the community where its neighboring nodes are located.

When the maximum module degree increasing value exceeds a preset threshold value, the recorded module degree value and the maximum module degree increasing value are accumulated, and the recorded module degree value is updated to be an accumulated value obtained by accumulation. Or determining the neighbor node corresponding to the maximum modularity increment value, and updating the recorded modularity value to the modularity value corresponding to the neighbor node.

And when the maximum modularity increasing value in the modularity increasing values corresponding to each neighbor node exceeds a preset threshold, randomly selecting one node from the second community set as a second node, and repeating the operations of the steps 305 and 306.

And when the maximum modularity increase value in the modularity increase values corresponding to each neighbor node does not exceed the preset threshold, increasing the second community identification times, and when the second community identification times do not reach the second preset times threshold, determining each identified community as one node in the second community set, and repeatedly executing the operations of the steps 301 to 306, wherein the initial value of the second community identification times is 0. And when the second community identification times reach a second preset times threshold value, taking the second community set at the moment as a third community set.

The second preset number of times threshold may be a value of 1, 2, or 3, etc.

For example, suppose communities in the second community set are clustered into communities 4, 5, 8, and 10. Assuming that community 4 includes nodes 1, 2, 3, 4, 7, 9, community 5 includes nodes 5, 11, community 8 includes nodes 6, 12, and community 10 includes nodes 10, 13, 14, 15. Taking each community of communities 4, 5, 8 and 10 as a node, four nodes are obtained, namely new nodes 4, 5, 8 and 10 respectively.

For any two communities in the four communities, if edge connection exists between nodes in the two communities, edge connection exists between two nodes corresponding to the two communities. For example, for communities 4 and 5, since there is an edge connection between node 7 in community 4 and node 5 in community 5, there is an edge connection between new node 4 corresponding to community 4 and new node 5 corresponding to community 5. Similarly, there is an edge connection between the new node 4 corresponding to the community 4 and the new node 8 corresponding to the community 8, there is an edge connection between the new node 4 corresponding to the community 4 and the new node 10 corresponding to the community 10, there is an edge connection between the new node 5 corresponding to the community 5 and the new node 8 corresponding to the community 8, there is an edge connection between the new node 5 corresponding to the community 5 and the new node 10 corresponding to the community 10, and there is an edge connection between the new node 8 corresponding to the community 8 and the new node 10 corresponding to the community 10, thereby obtaining a new second community set as shown in fig. 4, and then the operations of steps 305 to 306 are performed on the second community set as shown in fig. 4.

In the embodiment of the application, for any node in the first community set, namely the first node, the module degree increasing value of any two neighbor nodes of the first node is obtained, the first node is moved to the community where one neighbor node in the two neighbor nodes is located according to the module degree increasing value of the two neighbor nodes, and the number of nodes participating in operation is small because the community is clustered between the first node and the two neighbor nodes, so that a large number of nodes in the first community set can be clustered into communities rapidly to obtain the second community set. And then, in a second community set in which a large number of nodes are clustered into communities, for each node in the second community set, namely the second node, obtaining the modularity increase value of each neighbor node of the second node, and moving the second node into the community in which the neighbor node corresponding to the maximum modularity increase value is located.

The following are device embodiments of the present application, which may be used to perform method embodiments of the present application. For details not disclosed in the device embodiments of the present application, please refer to the method embodiments of the present application.

Referring to fig. 5, the present application provides an apparatus 500 for community aggregation, the apparatus 500 comprising:

an obtaining module 501, configured to obtain a first community set, where the first community set includes a plurality of communities, each community includes a node in a graph, and the graph is an undirected graph including a plurality of nodes;

a first mobile module 502, configured to obtain a modularity increase value of any two neighboring nodes of a first node, where the first node is any node in the graph; moving the first node from a first community to a community where one of the two neighbor nodes is located according to the modularity increment value of the two neighbor nodes in the first community set to obtain a second community set, wherein the first community is the community where the first node is located;

a second moving module 503, configured to obtain a modularity increase value of each neighboring node of a second node, where the second node is any node in the graph; and when the maximum modularity increasing value in the modularity increasing values corresponding to each neighbor node exceeds a preset threshold, moving the second node from a second community to the community where the neighbor node corresponding to the maximum modularity increasing value is located in the second community set to obtain a third community set, wherein the second community is the community where the second node is located.

As an example, the first mobile module 502 includes:

as an example, the first mobile module 502 further includes:

As an example, the apparatus 500 further comprises:

As an example, the second moving module 503 is configured to move a second node to a community where one neighboring node of the second node is located and obtain a module degree increment value of all communities currently, and determine the module degree increment value as the module degree increment value of the one neighboring node.

As an example, the determining module 501 is further configured to:

The specific manner in which the various modules perform the operations in the apparatus of the above embodiments have been described in detail in connection with the embodiments of the method, and will not be described in detail herein.

Fig. 6 shows a block diagram of a terminal 600 according to an exemplary embodiment of the present invention. The terminal 600 may be a portable mobile terminal such as: a smart phone, a tablet computer, an MP3 player (Moving Picture Experts Group Audio Layer III, motion picture expert compression standard audio plane 3), an MP4 (Moving Picture Experts Group Audio Layer IV, motion picture expert compression standard audio plane 4) player, a notebook computer, or a desktop computer. Terminal 600 may also be referred to by other names of user devices, portable terminals, laptop terminals, desktop terminals, etc.

In general, the terminal 600 includes: a processor 601 and a memory 602.

Processor 601 may include one or more processing cores, such as a 4-core processor, an 8-core processor, and the like. The processor 601 may be implemented in at least one hardware form of DSP (Digital Signal Processing ), FPGA (Field-Programmable Gate Array, field programmable gate array), PLA (Programmable Logic Array ). The processor 601 may also include a main processor, which is a processor for processing data in an awake state, also called a CPU (Central Processing Unit ), and a coprocessor; a coprocessor is a low-power processor for processing data in a standby state. In some embodiments, the processor 601 may integrate a GPU (Graphics Processing Unit, image processor) for rendering and drawing of content required to be displayed by the display screen. In some embodiments, the processor 601 may also include an AI (Artificial Intelligence ) processor for processing computing operations related to machine learning.

The memory 602 may include one or more computer-readable storage media, which may be non-transitory. The memory 602 may also include high-speed random access memory, as well as non-volatile memory, such as one or more magnetic disk storage devices, flash memory storage devices. In some embodiments, a non-transitory computer readable storage medium in memory 602 is used to store at least one instruction for execution by processor 601 to implement the method of community identification provided by the method embodiments herein.

In some embodiments, the terminal 600 may further optionally include: a peripheral interface 603, and at least one peripheral. The processor 601, memory 602, and peripheral interface 603 may be connected by a bus or signal line. The individual peripheral devices may be connected to the peripheral device interface 603 via buses, signal lines or a circuit board. Specifically, the peripheral device includes: at least one of radio frequency circuitry 604, a touch display 605, a camera 606, audio circuitry 607, a positioning component 608, and a power supply 609.

Peripheral interface 603 may be used to connect at least one Input/Output (I/O) related peripheral to processor 601 and memory 602. In some embodiments, the processor 601, memory 602, and peripheral interface 603 are integrated on the same chip or circuit board; in some other embodiments, either or both of the processor 601, memory 602, and peripheral interface 603 may be implemented on separate chips or circuit boards, which is not limited in this embodiment.

The Radio Frequency circuit 604 is configured to receive and transmit RF (Radio Frequency) signals, also known as electromagnetic signals. The radio frequency circuit 604 communicates with a communication network and other communication devices via electromagnetic signals. The radio frequency circuit 604 converts an electrical signal into an electromagnetic signal for transmission, or converts a received electromagnetic signal into an electrical signal. Optionally, the radio frequency circuit 604 includes: antenna systems, RF transceivers, one or more amplifiers, tuners, oscillators, digital signal processors, codec chipsets, subscriber identity module cards, and so forth. The radio frequency circuit 604 may communicate with other terminals via at least one wireless communication protocol. The wireless communication protocol includes, but is not limited to: the world wide web, metropolitan area networks, intranets, generation mobile communication networks (2G, 3G, 4G, and 5G), wireless local area networks, and/or WiFi (Wireless Fidelity ) networks. In some embodiments, the radio frequency circuitry 604 may also include NFC (Near Field Communication, short range wireless communication) related circuitry, which is not limited in this application.

The display screen 605 is used to display a UI (User Interface). The UI may include graphics, text, icons, video, and any combination thereof. When the display 605 is a touch display, the display 605 also has the ability to collect touch signals at or above the surface of the display 605. The touch signal may be input as a control signal to the processor 601 for processing. At this point, the display 605 may also be used to provide virtual buttons and/or virtual keyboards, also referred to as soft buttons and/or soft keyboards. In some embodiments, the display 605 may be one, providing a front panel of the terminal 600; in other embodiments, the display 605 may be at least two, respectively disposed on different surfaces of the terminal 600 or in a folded design; in still other embodiments, the display 605 may be a flexible display, disposed on a curved surface or a folded surface of the terminal 600. Even more, the display 605 may be arranged in a non-rectangular irregular pattern, i.e., a shaped screen. The display 605 may be made of LCD (Liquid Crystal Display ), OLED (Organic Light-Emitting Diode) or other materials.

The camera assembly 606 is used to capture images or video. Optionally, the camera assembly 606 includes a front camera and a rear camera. Typically, the front camera is disposed on the front panel of the terminal and the rear camera is disposed on the rear surface of the terminal. In some embodiments, the at least two rear cameras are any one of a main camera, a depth camera, a wide-angle camera and a tele camera, so as to realize that the main camera and the depth camera are fused to realize a background blurring function, and the main camera and the wide-angle camera are fused to realize a panoramic shooting and Virtual Reality (VR) shooting function or other fusion shooting functions. In some embodiments, camera assembly 606 may also include a flash. The flash lamp can be a single-color temperature flash lamp or a double-color temperature flash lamp. The dual-color temperature flash lamp refers to a combination of a warm light flash lamp and a cold light flash lamp, and can be used for light compensation under different color temperatures.

The audio circuit 607 may include a microphone and a speaker. The microphone is used for collecting sound waves of users and environments, converting the sound waves into electric signals, and inputting the electric signals to the processor 601 for processing, or inputting the electric signals to the radio frequency circuit 604 for voice communication. For the purpose of stereo acquisition or noise reduction, a plurality of microphones may be respectively disposed at different portions of the terminal 600. The microphone may also be an array microphone or an omni-directional pickup microphone. The speaker is used to convert electrical signals from the processor 601 or the radio frequency circuit 604 into sound waves. The speaker may be a conventional thin film speaker or a piezoelectric ceramic speaker. When the speaker is a piezoelectric ceramic speaker, not only the electric signal can be converted into a sound wave audible to humans, but also the electric signal can be converted into a sound wave inaudible to humans for ranging and other purposes. In some embodiments, the audio circuit 607 may also include a headphone jack.

The location component 608 is used to locate the current geographic location of the terminal 600 to enable navigation or LBS (Location Based Service, location based services). The positioning component 608 may be a positioning component based on the United states GPS (Global Positioning System ), the Beidou system of China, or the Galileo system of Russia.

A power supply 609 is used to power the various components in the terminal 600. The power source 609 may be alternating current, direct current, disposable battery or rechargeable battery. When the power source 609 includes a rechargeable battery, the rechargeable battery may be a wired rechargeable battery or a wireless rechargeable battery. The wired rechargeable battery is a battery charged through a wired line, and the wireless rechargeable battery is a battery charged through a wireless coil. The rechargeable battery may also be used to support fast charge technology.

In some embodiments, the terminal 600 further includes one or more sensors 610. The one or more sensors 610 include, but are not limited to: acceleration sensor 611, gyroscope sensor 612, pressure sensor 613, fingerprint sensor 614, optical sensor 615, and proximity sensor 616.

The acceleration sensor 611 can detect the magnitudes of accelerations on three coordinate axes of the coordinate system established with the terminal 600. For example, the acceleration sensor 611 may be used to detect components of gravitational acceleration in three coordinate axes. The processor 601 may control the touch display screen 605 to display a user interface in a landscape view or a portrait view according to the gravitational acceleration signal acquired by the acceleration sensor 611. The acceleration sensor 611 may also be used for the acquisition of motion data of a game or a user.

The gyro sensor 612 may detect a body direction and a rotation angle of the terminal 600, and the gyro sensor 612 may collect a 3D motion of the user on the terminal 600 in cooperation with the acceleration sensor 611. The processor 601 may implement the following functions based on the data collected by the gyro sensor 612: motion sensing (e.g., changing UI according to a tilting operation by a user), image stabilization at shooting, game control, and inertial navigation.

The pressure sensor 613 may be disposed at a side frame of the terminal 600 and/or at a lower layer of the touch screen 605. When the pressure sensor 613 is disposed at a side frame of the terminal 600, a grip signal of the terminal 600 by a user may be detected, and a left-right hand recognition or a shortcut operation may be performed by the processor 601 according to the grip signal collected by the pressure sensor 613. When the pressure sensor 613 is disposed at the lower layer of the touch display screen 605, the processor 601 controls the operability control on the UI interface according to the pressure operation of the user on the touch display screen 605. The operability controls include at least one of a button control, a scroll bar control, an icon control, and a menu control.

The fingerprint sensor 614 is used for collecting the fingerprint of the user, and the processor 601 identifies the identity of the user according to the fingerprint collected by the fingerprint sensor 614, or the fingerprint sensor 614 identifies the identity of the user according to the collected fingerprint. Upon recognizing that the user's identity is a trusted identity, the processor 601 authorizes the user to perform relevant sensitive operations including unlocking the screen, viewing encrypted information, downloading software, paying for and changing settings, etc. The fingerprint sensor 614 may be provided on the front, back, or side of the terminal 600. When a physical key or vendor Logo is provided on the terminal 600, the fingerprint sensor 614 may be integrated with the physical key or vendor Logo.

The optical sensor 615 is used to collect ambient light intensity. In one embodiment, processor 601 may control the display brightness of touch display 605 based on the intensity of ambient light collected by optical sensor 615. Specifically, when the intensity of the ambient light is high, the display brightness of the touch display screen 605 is turned up; when the ambient light intensity is low, the display brightness of the touch display screen 605 is turned down. In another embodiment, the processor 601 may also dynamically adjust the shooting parameters of the camera assembly 606 based on the ambient light intensity collected by the optical sensor 615.

A proximity sensor 616, also referred to as a distance sensor, is typically provided on the front panel of the terminal 600. The proximity sensor 616 is used to collect the distance between the user and the front of the terminal 600. In one embodiment, when the proximity sensor 616 detects a gradual decrease in the distance between the user and the front face of the terminal 600, the processor 601 controls the touch display 605 to switch from the bright screen state to the off screen state; when the proximity sensor 616 detects that the distance between the user and the front surface of the terminal 600 gradually increases, the processor 601 controls the touch display screen 605 to switch from the off-screen state to the on-screen state.

Those skilled in the art will appreciate that the structure shown in fig. 6 is not limiting of the terminal 600 and may include more or fewer components than shown, or may combine certain components, or may employ a different arrangement of components.

Other embodiments of the present application will be apparent to those skilled in the art from consideration of the specification and practice of the application disclosed herein. This application is intended to cover any variations, uses, or adaptations of the application following, in general, the principles of the application and including such departures from the present disclosure as come within known or customary practice within the art to which the application pertains. It is intended that the specification and examples be considered as exemplary only, with a true scope and spirit of the application being indicated by the following claims.

It is to be understood that the present application is not limited to the precise arrangements and instrumentalities shown in the drawings, which have been described above, and that various modifications and changes may be effected without departing from the scope thereof. The scope of the application is limited only by the appended claims.

Claims

1. A method of community aggregation, the method comprising:

acquiring a first community set, wherein the first community set comprises a plurality of communities, each community comprises a node in a graph, the graph is an undirected graph comprising a plurality of nodes, each node in the graph is a user, and the nodes are connected with neighboring nodes by edges to indicate that certain connection exists between the two users;

acquiring a modularity increasing value of each neighbor node of a second node, wherein the second node is any node in the graph; when the maximum modularity increasing value in the modularity increasing values corresponding to each neighbor node exceeds a preset threshold, moving the second node from a second community to a community where the neighbor node corresponding to the maximum modularity increasing value is located in the second community set to obtain a third community set, wherein the second community is the community where the second node is located;

the method further includes, after the moving the first node from the first community to the community where one of the two neighboring nodes is located according to the module value of the two neighboring nodes,:

Executing the module degree increment value of any two neighbor nodes of a first node on each node, adding the first node to communities where one neighbor node of the two neighbor nodes is located according to the module degree increment value of the two neighbor nodes, increasing first community identification times, randomly selecting one node from nodes included in a first community set as the first node when the first community identification times do not reach a first preset times threshold, and executing the operation of acquiring the module degree increment value of any two neighbor nodes of the first node; and when the first community identification times reach a first preset times threshold, taking the first community set as a second community set, and executing the module degree increment value of each neighbor node of the second node.

2. The method of claim 1, wherein the obtaining the module increment value of any two neighboring nodes of the first node comprises:

And moving the first node from the community where the first neighbor node is located to the community where the second neighbor node is located and obtaining second module degree added values of all communities at present, wherein the second module degree added values are module degree added values of the second neighbor node, and the second neighbor node is another neighbor node of the first node.

3. The method of claim 2, wherein the adding the first node to the community in which one of the two neighbor nodes is located according to the module degree increment value of the two neighbor nodes comprises:

4. A method according to any one of claims 1 to 3, wherein said obtaining a modularity increase value for each neighbor node of the second node comprises:

5. A method according to any one of claims 1 to 3, wherein the method further comprises:

6. An apparatus for community aggregation, the apparatus comprising:

the system comprises an acquisition module, a first community set and a second community set, wherein the first community set comprises a plurality of communities, each community comprises a node in a graph, the graph is an undirected graph comprising a plurality of nodes, each node in the graph is a user, and the nodes are connected with neighbor nodes by edges to indicate that certain connection exists between the two users;

The selection module is used for executing the module degree increasing value of any two neighbor nodes of the first node on each node, adding the first node to communities where one neighbor node of the two neighbor nodes is located according to the module degree increasing value of the two neighbor nodes, increasing the first community identification times, randomly selecting one node from the nodes included in the first community set as the first node when the first community identification times do not reach a first preset times threshold, and executing the operation of acquiring the module degree increasing value of any two neighbor nodes of the first node; when the first community identification times reach a first preset times threshold, taking the first community set as a second community set, and executing the module degree increment value of each neighbor node of the second node;

7. The apparatus of claim 6, wherein the first mobile module comprises:

the second mobile unit is used for moving the first node from the community where the first neighbor node is located to the community where the second neighbor node is located and obtaining second module degree added values of all communities currently, the second module degree added values are module degree added values of the second neighbor node, and the second neighbor node is another neighbor node of the first node.

8. The apparatus of claim 7, wherein the first mobile module further comprises:

9. The apparatus according to any one of claims 6 to 8, wherein the second moving module is configured to move a second node to a community where one neighboring node of the second node is located and obtain a module degree increment value of all communities currently, and determine the module degree increment value as the module degree increment value of the one neighboring node.

10. The apparatus according to any one of claims 6 to 8, wherein the apparatus further comprises: a determining module for: