CN104217073B - A Visual Layout Method of Network Community Gravity Guidance - Google Patents

Abstract

The invention relates to the field of information visualization, in particular to a visualization layout method capable of reflecting complex network community structures. The present invention adds community gravity to each node on the basis of the force-guided layout algorithm, so that the nodes of the same community gather toward the center of the community, introduces the k-means algorithm into the community gravity, and realizes the aggregation of nodes while laying out kind. In order to prevent and reduce overlap, the community gravitational coefficient is introduced to control the size of the community gravitation. The invention not only can display the community structure of the complex network, but also has the characteristics of simplicity, easy realization, fast convergence speed and the like.

Description

A Visual Layout Method of Network Community Gravity Guidance

technical field

The invention relates to the field of information visualization, in particular to a visualization layout method capable of reflecting complex network community structures.

Background technique

The visual layout method is widely used in the field of social relationship network, which can be used to show the closeness of the relationship between individuals and intuitively show the process of network information dissemination, etc. At present, the most common method of visual layout is to use the force-directed method to display the network structure, and has achieved good analysis results. However, most of the force-guided methods do not take into account the graph clustering phenomenon, and the layout principle of uniform distribution of nodes prevents the display of network clustering characteristics.

In order to solve the problem that most of the force-guided visual layout methods cannot show the community structure of complex networks, researchers introduced a community partition algorithm and proposed a method of first network clustering and then visual layout to show the community structure of complex networks. Zhu Zhiliang and others published an article entitled "Visual Layout Algorithm of Network Topology Structure Based on Complex Network Community Division" in "Journal of Computer-Aided Design and Graphics", Volume 23, Issue 11. This paper proposed a community-based network layout algorithm. Firstly, the complex network community discovery algorithm is used to divide the nodes in the network into communities, and a community is abstracted into a node, and a new network is constructed with the association between communities; on this basis, the center point of the community is determined by using the physical analogy method The location of the community, and the regional scope of the community is determined according to the size of the community; finally, the internal nodes of the community are filled in the way of condition selection to complete the layout of the network topology. This layout method can display the community structure of the network, but it separates the community division and the layout algorithm, and the layout results cannot effectively display the edge nodes. The Chinese invention patent with the publication number CN101741623A discloses a network visualization method in the field of network technology, which adopts the community division method based on the modularity index to divide the network layer, and also relies on the existing community division method to aggregate the network first. class, and then layout. The layout steps are too complicated, and there are disadvantages such as low layout efficiency.

Therefore, the method of first network clustering and then visual layout has the following problems when displaying the network community structure: (1) the layout method is too dependent on the existing community division algorithm; (2) the layout results are too subjective, and some network structures Information is lost; (3) The algorithm steps are complex and not suitable for large networks.

Contents of the invention

The technical problem to be solved by the present invention is to solve the limitations of the network clustering first and then the visual layout method, realize the layout and complete the display of the complex network community structure at the same time, and propose a visual layout method guided by community gravity.

This method is based on the force-guided layout, adding community gravity to each node, and introducing the principle of k-means algorithm, so that the nodes of the same community can gather towards the center of the community. The community gravitational force is controlled by the community gravitational coefficient to prevent and reduce overlapping and achieve a good layout effect. For community gravity clustering, set the quality of nodes according to their importance, then calculate the distance from the node to the center of the community to which it belongs, and finally set a reasonable community gravity coefficient to obtain the community gravity of each node. The nodes will gather towards the center of the community under the guidance of the community's gravity. Specific methods include:

A visual layout method guided by community gravity, which determines the quality of nodes according to the node centrality; determines the center position of the community according to the number of nodes in the community and the position of the nodes, and selects the community according to the distance from the node to the center of the community; calculates the network According to the attraction and repulsion of other nodes in the node, the nodes are laid out according to the attraction and repulsion; the community gravity of the community to the node is calculated, and the nodes gather towards the center of the community under the guidance of the community gravity, so that the nodes of the same community gather together. To achieve the effect of clustering.

According to the actual distance d and the ideal distance r of two nodes, call the formula: Calculate the attractive force f _a (d) from the edge and the repulsive force f _r (d) from the node; according to the mass M[v] of the node v, the distance d _k from the node v to the center position u _k of the community C _k , call the formula : f _g (d)=gM[v]min(d ₁ , d ₂ , . . . , d _k ) calculates the community gravitational force of the community on node v, where g is the community gravitational coefficient.

The node layout is affected by three forces, which are the gravitational force between nodes connected by edges, the repulsive force between all nodes, and the community gravitational force between all nodes and their communities. For the determination of the location of the community center, the k-means algorithm is introduced to obtain the community center. Determining the location of the community center specifically includes steps: (1) randomly select k nodes as the initial community center; (2) select the initial community center closest to the node as the community center of the node, and the node belongs to the community; (3) when After the community ownership of all nodes is determined, call the formula Determine the center position of the kth community, n represents the number of nodes of community k, p _v represents the position of node v; (4) repeat steps (2)-(3) to determine the center position of each community, when the system temperature reaches the minimum value , the positions of all community centers are determined.

To prevent and reduce overlap, it is necessary to adjust the size of the community gravitational coefficient. In general, the more nodes, the smaller the community gravitational coefficient. After experiments, the optimal value of community gravitational coefficient is generally between 0 and 2.

The invention combines network clustering with visual layout, improves the objectivity of layout results, prevents loss of edge node information, and has simple algorithm, easy implementation and fast convergence speed.

Description of drawings

Figure 1 is a flow chart of the visual layout method of community gravity guidance;

Fig. 2 is the layout effect of the layout of the present invention on the Zachary dataset.

detailed description

The content of the present invention will be described in further detail below in conjunction with the accompanying drawings.

The whole system will reach equilibrium under the interaction of repulsion, gravity and community gravity, where community gravity is used to guide nodes to gather towards the center of the community. Secondly, instead of directly obtaining the location of the community center by dividing the nodes into communities, the principle of the k-means algorithm is introduced into the community gravity to complete the determination of the community center. Finally, for the problem of node overlap, the community gravitational coefficient is adjusted to prevent the nodes from transitioning to the center of the community.

First, the quality of each node is determined by the importance of the node. According to the node centrality (degree centrality), closeness centrality (closeness centrality) and distance centrality (betweenness centrality) in network analysis as the standard to measure the importance of nodes, the layout generated by different quality division standards can show network clustering characteristic. Secondly, determine the distance from the node to the center of the community, and the generation of the clustering effect is mainly determined by the distance. Then the community gravity of each node is obtained according to the community gravity coefficient. The value of the community gravitational coefficient mainly depends on the number of nodes. Generally speaking, the more nodes there are, the smaller the value of the community gravitational coefficient.

Let G be a network, represented by nodes and edges as G(V,E), where V is a set of n nodes {v ₁ ,v ₂ ,...,v _n }, and E is a set of m edges{ e ₁ ,e ₂ ,...,e _m }, G can be divided into k communities {C ₁ ,C ₂ ,…,C _k }, and the corresponding community centers are {u ₁ ,u ₂ ,…,u _k }. If the layout problem is equivalent to the force of objects in physics, then the node will reach equilibrium under the action of three forces: the repulsion from other nodes, the attraction from the edge and the community gravity from the community. The specific implementation steps are shown in Figure 1 as follows:

A1: It is the initialization stage. According to the node centrality method in network analysis, the quality of the node is determined, that is, the greater the corresponding centrality, the greater the quality of the node.

A2: Calculate the gravitational and repulsive forces on the nodes. The gravitational and repulsive forces are mainly used to maintain the balance of the system and reduce edge crossings. According to the actual distance d and the ideal distance r of two nodes, call the FR algorithm of formula (1) to calculate the attractive force f _a (d) and the repulsive force f _r (d). According to the attractive force f _a (d) and the repulsive force f _r (d) to the node layout, the layout principle is that the nodes with edges should be adjacent, but a certain distance should be kept. The optimal distance depends on the number of nodes and the size of the canvas. The repulsive force exists on all nodes, and the attractive force only exists on the nodes with edges. The moving range of each layout iteration node will gradually decrease as the temperature decreases, and the system temperature will be reduced to the lowest level, and the layout will reach the best state.

A3: Determine the location of the community center. The community center is obtained by using the k-means algorithm. The specific method for determining the location of the community center is as follows: (1) Randomly select K nodes as the initial community center, K represents the number of communities; (2) Calculate the distance between other nodes and the K community centers, and select the initial node with the closest distance to the node The community center is the community center of the node, and the node belongs to the community; (3) After the community ownership of all nodes is determined, determine the center position of each community, and call the formula Determine the center position of the kth community, n represents the number of nodes of community k, p _v represents the position of node v; (4) repeat steps (2)-(3), when the system temperature reaches the minimum value, the center positions of all communities are determined .

A4: Further adjust the layout according to the community gravity f _g (d), so that the nodes of the same community can be gathered together to achieve the effect of clustering. According to the mass M[v] of node v, the distance d _k from node v to the center point u _k of the community, call the formula (2) to calculate the community gravitational force from the community to node v, where g is the community gravitational coefficient, d _k is the distance between node v and community k:

f _g (d)=gM[v]min(d ₁ , d ₂ , . . . , d _k ) (2)

A5: Adjust the value of the community gravitational coefficient g to prevent the nodes from gathering together. The size of g mainly depends on the number of nodes. Generally speaking, the more nodes there are, the smaller the value of g is. Its value is usually between 0 and 2.

A6: When the temperature of the system reaches the given minimum value, the node adjustment ends, otherwise, go to step A2. For temperature adjustment, the principle of simulated annealing can be used, that is, a relatively high temperature value is given first, and then the temperature value is slowly lowered until it reaches the minimum value.

In order to quantify the strength of the community structure generated under this convergence condition, the modularity Q is introduced to evaluate the strength of the community structure.

Among them, k _i and k _j represent the degrees of nodes i and j, Ci and Cj represent the communities to which nodes i and j belong, and m is the total number of edges in the network G. When i and j belong to the same community, δ(C _i C _j )=1, otherwise δ(C _i C _j )=0. A _ij represents the connection between i and j, when there is an edge between i and j, A _ij =1, otherwise A _ij =0. Modularity is widely used in community detection, and its value is between 0 and 1. Generally, when the modularity value is above 0.3, the community structure can be found.

Fig. 2 is the layout effect of the layout of the present invention on the Zachary dataset. The public dataset Zachary was chosen for experimentation. The Zachary network describes the mutual social relationship among members of a karate club in an American university, including 34 nodes and 78 edges. Nodes represent club members, and edges represent mutual acquaintances between two members. The layout effect is shown in Figure 2. It can be seen that the algorithm can clearly reflect the community structure characteristics of complex networks.

Claims (3)

1. A visual layout method guided by community gravity, characterized in that: according to the node centrality, the quality is determined for the node; according to the number of community nodes, the position of the node determines the center position of the community, and the node is selected according to its distance to the center position of the community The community to which it belongs; according to the actual distance d and the ideal distance r between the node and other nodes, call the formula: Calculate the attraction f _a (d) from the edge to the node and the repulsion f _r (d) from other nodes to the node; arrange the nodes according to the attraction and repulsion; according to the mass M[v] of the node v, the node v The distance d _k to the center position u _k of the community C _k , call the formula: f _g (d)=gM[v]min(d ₁ , d ₂ ,...,d _k ) calculates the community gravitational force of the community on node v, where g is the community gravitational coefficient; the node is guided by the community gravitational force , gather to the center of the community, so that the nodes of the same community gather together to achieve clustering. 2. The method according to claim 1, wherein the repulsive force exists between all nodes, and the attractive force only exists between nodes with edges. The centers are gathered together, the system temperature is minimized, and the layout is completed. 3. The method according to claim 1 or 2, wherein determining the location of the community center specifically includes the steps of: (1) randomly selecting k nodes as the initial community center; (2) selecting the initial community center closest to the node As the community center of the node, the node belongs to the community; (3) After the community ownership of all nodes is determined, call the formula Determine the central position of the kth community, where n represents the number of nodes in community k, and pv represents the position of node _v ; (4) repeat steps (2)-(3) to determine the central position of each community, when the system temperature reaches The minimum value, the positions of all community centers are determined.