An Improved FN Algorithm for Community Division of Air Route Network

，，，

College of Civil Aviation/College of Flight，Nanjing University of Aeronautics and Astronautics，Nanjing 211106，P.R.China

（Received 3 June 2020；revised 5 July 2020；accepted 25 July 2020）

Abstract: Community division is an important method to study the characteristics of complex networks. The widely used fast-Newman（FN）algorithm only considers the topology division of the network at the static layer，and dynamic traffic flow demand is ignored. The result of the division is only structurally optimal. To improve the accuracy of community division，based on the static topology of air route network，the concept of network traffic contribution degree is put forward. The concept of operational research is introduced to optimize the network adjacency matrix to form an improved community division algorithm. The air route network in East China is selected as the object of algorithm comparison experiment，including 352 waypoints and 928 segments. The results show that the improved algorithm has a more ideal effect on the division of the community structure. The proportion of the number of nodes included in the large community has increased by 21.3%，and the modularity value has increased from 0.756 to 0.806，in which the modularity value is in the range of［-0.5，1）. The research results can provide theoretical and technical support for the optimization of flight schedules and the rational use of air route resources.

Key words:air route network；community division；topological structure；traffic flow contribution

0 Introduction

The air route network has significant impact on the safety and efficiency of aircraft operation. The traditional research on air route network mostly focuses on regional assessment，and seldom takes into account the interaction between different regions，which cannot fundamentally solve the problems such as airspace congestion and flight delay. The air route network is a typical complex network［1］，and the community network theory belongs to the frontier of complex network theory. Studying the characteristics of the community structure of the air route network is helpful to analyze the mutual influences between the various areas of the air route network.Therefore，scholars pay more and more attention to it.

The classical algorithms for community structure division are mainly as follows. In 2002，Newman and Girvan［2］proposed an important GN community division algorithm based on the idea of splitting. According to some connection properties，the key paths connecting the two communities were found out from all edges and eliminated one by one，and the network community structure with the best effect was divided. In 2004，Newman［3］improved the GN algorithm and proposed the fast-Newman（FN） community division algorithm，which is a kind of condensation algorithm. The core idea is that every independent node in the network is regarded as an initial community，and then the result of the maximum modularity increment is taken as the next direction of agglomeration. The latest community contains all the nodes. The community structure with the greatest value-added is taken as the final result of the community division. Yang et al.［4］developed an accurate and scalable algorithm for detecting overlapping communities in networks with node attributes，which is called communities from edge structure and node attributes（CESNA）. Su et al.［5］proposed the multi-level community discovery algorithm in 2018，which relies on a combination of user interests and cohesiveness in describing community structures. To sum up，the existing community division algorithms mainly focus on the topological characteristics of the air route network［6］，without considering the impact of the traffic flow of the air route network on the overall operation state of the network. In view of the shortcomings，based on the static topology of the air route network，this paper puts forward the concept of network traffic flow contribution degree，and divides the community of the air route network by combining the static structure index and dynamic flow to improve the FN algorithm.

1 Related Concepts of Community Division

1.1 Community structure

A community is a collection of units with some common characteristics［7］. The more commonly used definition of community structure is based on the relative connection frequency:the vertices in the network can be divided into groups，the connections within the groups are dense and the connections between groups are sparse. A simple schematic diagram of the community structure［8］is shown in Fig.1.

According to the formation process of community in complex network，the idea of community structure in network can be divided into four categories［9］:Cohesion process，splitting process，search process and other processes. The condensation process is based on vertices and forms a community through gradual condensation. On the contrary，in the splitting process，all the vertices in the network are regarded as a large community，and a small community is formed through gradual segmentation.The search process is an exploration process of establishing a gradual optimization goal，and the community structure is given directly by the final optimization results.

Fig.1 Schematic diagram of community structure

1.2 Modularity function

Regarding the measurement standard of community structure，most adopt the modularity functionQdefined by Newman［10］. Modularity refers to the expectation of the difference between the proportion of the edge connected to the nodes within the community structure and the proportion of any edge connected to the nodes in the network. TheQfunction is used to quantitatively describe the modular level of community division. The value of modularity is in the range of［-0.5，1）.The larger theQvalue，the better the community division effect.

2 Improved Fast-Newman Algorithm

FN algorithm is not only a greedy algorithm for finding the largest module value，but also a condensation one for adding edges to the network. Its core idea is a bottom-up hierarchical clustering process，which detects the community structure by maximizing the modularization. It can greatly reduce the time complexity and can be used to analyze complex networks with millions of nodes.

The specific FN algorithm process is as follows.

Step 1Consider a complex network ofnnodes asncommunities，the initial situation is

wherekiis the degree of nodeiandmthe total number of edges contained in the complex network.

Step 2According to the principle of greedy algorithm，two communities with edge connections are merged in turn along the direction that makesQincrease or decrease fastest，and theQvalue increment after the merger is calculated.The formula is

Step 3Replace the corresponding data and add the rows and columns of theiandjcommunities.

Step 4Repeat Steps 2 and 3 until each node is merged into a community.

2.1 Traffic flow contribution

The general definition of the network traffic flow is as follows. Assume that all nodes have the ability to pass，and the initial traffic flow is 0. For every carrier passing，the traffic flow of the node increases by 1. In air route network，traffic flow generally refers to the number of aircraft passing a certain flight segment or a certain waypoint per unit time. The traffic flow of the air route network node is defined as“flow”，and the flow of theith node is expressed as“flowi”.

For the FN algorithm，only the topological structure division of the static level of the network is considered，which leads to the problem that the community division is often not the optimal community structure. In order to improve the accuracy of community division，based on the static topology of the route network，this paper adds the network dynamic traffic flow contribution as the basis of community division，and proposes an improved FN algorithm named flow-contribution fast-Newman（FC-FN）algorithm.

In the basic FN algorithm，Qis obtained by static topology calculation，but in the actual operation of the network，the traffic flow of each node in the network is different and not fixed，so the importance of each node to the network［11-12］is different.

Define the variablefcito represent the contribution of theinode to theQvalue in the network.

2.2 Process description of FC-FN algorithm

It is assumed that the connections between the nodes in the network and the edges in the network are known. The network can be defined asG(V，E)，whereV={vi|i=1，2，3，…，n} is a collection of nodes；nthe number of nodes；E={eij|i，j=1，2，3，…，m，i≠j} the edge of the network；andmthe number of edges.

In operational research，according to the relationship between total supply and total demand，the transportation problem can be divided into two categories:balanced transportation problem and unbalanced transportation problem. The latter is usually transformed into the former by adding virtual supply nodes or virtual demand nodes. Community division is a complex network problem.To analyze the influence of different“flowi”onQmore effectively，the idea of“balance of supply and demand”［13］is introduced. Classify the node traffic flow，and increase the number of“virtual nodes”to the nodes with large traffic flow.

Step 1The traffic flow of nodes is a discrete variable，and the median［14］of traffic flow of all nodes in the network is selected as the base of flow classification. This is a method to measure the trend of traffic flow concentration. The median is the representative value of all data determined by its location in the data set，which is not affected by the maximum or minimum of data distribution. When the individual data in a group of data changes greatly，the median can be used to describe the central tendency of this group of data. In the process of calculating the traffic flow of the air route network，data distortion may occur. Choosing the median can avoid errors caused by the extremely large or small individual data to the overall calculation.

Define the traffic flow base of node classification as flowbase. In order to ensure that the increased“virtual node”can have common characteristics with the original node，“virtual connection”between the nodes should be added as the same as the original connection. The formula for calculating the base flow of node classification is

Step 2The ROUND function is used to round up the number of“virtual nodes”needed to calculate nodei，which is the traffic flow contributionfci.The calculation formula is

Considering the situation that the traffic flow of the network node is less than half of the flowbaseof the node，fci=0，but the actual running flow flowi≠0. To ensure the effectiveness of the calculation，makefci=1. The formula for calculatingfciis

wherei=1，2，…，n.

Step 3Optimize the network adjacency matrix. Define matrixl= (lij) as the initial adjacency matrix of the network.The formula oflijis

A new adjacency matrixl′=(l′ij) is obtained by adding the traffic flow contribution. The formula ofis

Step 4The result of network community division includeskcommunities. A symmetric matrixe=(eij) withkdimensions is defined，where the matrix elementeijrepresents the proportion of the number of edges connected between theicommunity and thejcommunity to the total number of edges contained in the network. The formula for calculating the sum of elements on the diagonal of a matrix is

This formula represents the proportion of the number of connected edges between the nodes within the community in the total number of edges in the network.

Assuming thataiis the sum of the elements in each row or column，which represents the proportion of the edges connected to the nodes in theicommunity in all edges，theQfunction can be expressed as

where ||e2|| represents the sum of all the elements in the matrixe2. The upper limit of theQvalue is 1.When the value ofQtends to 1，it indicates that the community structure of the entire network is more obvious，and the corresponding division effect of the community structure is better. If the proportion of edges within the community is not greater than the expected value of the proportion of any edges connecting nodes，thenQ≤0.

Calculate theQvalue of the modularity function under the FC-FN algorithm and record asQ′，the formula ofQ′is

3 Case Study and Verification

3.1 Overview of air route network in East China

The air route network is mainly composed of waypoints and flight segments. The waypoints represent the nodes in the network，and the flight segments connecting the waypoints represent the edges in the network.

The air route network in East China in October 2017 is selected as the research object. The airspace in the East China region borders the South-Central region to the south and the North China region to the north，including the busy airport clusters such as the Yangtze River Delta. It is one of the busiest airspaces in my country，and the data is researchable. On the basis of deduplication and correction of the original data，352 waypoints and 928 segments in East China route network are selected for research. The topological structure is shown in Fig.2，in which the circle represents the waypoint and the link between the circles represents the segments.

Fig.2 Topological structure diagram of East China air route network

3.2 Community division of air route network in East China

FN algorithm and FC-FN algorithm are used to divide the community of the air route network in East China.

The division situation is analyzed from two aspects:the results of community division and the modularity function.

3.2.1 FC-FN algorithm processing

Due to the large amount of data，select the processing process of the route points“RUPUD”（serial number 17）and“OF”（serial number 18）under the FC-FN algorithm as a demonstration.

Step 1Calculate the traffic flow base of node classification.flowbase=MEDIAN(flowi)=190i=1,2,…,352

Step 2Calculate the traffic flow contribution of node，and add“virtual node”and“virtual connection”as shown in Fig.3.

Step 3Optimize the adjacency matrix according to the traffic flow contribution.

The adjacency matrix of the network is the main influence factor of the algorithm，which represents the matrix of the adjacency relationship between vertices. For an undirected simple graph，the adjacency matrix must be symmetric and the main diagonal must be zero. Fig.4 shows the transformation of the adjacency matrix withfc17andfc18.

Fig.3 Schematic diagram of adding“virtual node”and“virtual connection”between nodes 17 and 18

Fig.4 Schematic diagram of adjacency matrix transformation with fc (nodes 17 and 18)

3.2.2 Analysis of community division results

To facilitate the visual display of the results of community division，each node is colored，and different colors correspond to different communities.

The FN algorithm divides the route network in East China into 11 communities，as shown in Fig.5，and the specific community contains the node information shown in Table 1. The FC-FN algorithm divides the route network in East China into 8 communities，as shown in Fig.6，and the specific community contains the node information shown in Table 2.

Compared with Figs.5 and 6，it can be found that there are some nodes in the community divided by FN algorithm that are not ideal. The community divided by FC-FN algorithm has close internal connections and few external connections，and there are no obvious outliers.

Fig.5 Community division graph of FN algorithm

Table 1 Result of community division (FN)

Fig.6 Community division graph of FC-FN algorithm

Table 2 Result of community division (FC-FN)

According to the results of community division，communities with more than or equal to 45 internal nodes are selected as large communities.

As shown in Table 1，the number of nodes within each community divided by FN algorithm is relatively small. Large communities have communities of Nos.5，8，10 and 11，accounting for 36.36%of the total number of communities，with a total of 196 nodes，accounting for about 55.6% of the total number of nodes. As shown in Table 2，the FCFN algorithm divides a large number of nodes within each community，among which large communities have communities of Nos.1，2，3，7 and 8，accounting for about 62.5% of the total number of communities，and the total number of nodes is 271，accounting for about 76.9% of the total number of nodes. The data comparison is shown in Table 3.

Table 3 Comparison of large organizations

3.2.3 Analysis of modularity function

Calculate theQvalue of the modularity function of the route network in East China under the FN algorithm and FC-FN algorithm respectively.The results are shown in Fig.7. When the FC-FN algorithm guarantees substantially the same number of iterations，the modularity of the air route network in East China is increased from 0.756 to 0.806，which is closer to 1. It shows that the community structure divided under the FC-FN algorithm is stronger than that of under the FN algorithm.

Fig.7 Schematic diagram of community structure

4 Conclusions

Based on the static topology of the route network，this paper proposes the concept of traffic flow contribution，and considers the impact of traffic flow on the network community division from a dynamic perspective.This method also introduces a solution to the problem of“balance between supply and demand”，classifies the flow of nodes，and increases the number of“virtual nodes”for nodes with large flows，optimizes the network adjacency matrix，and forms an improved FC-FN algorithm.The steps of the algorithm and the optimization formula are given. The FC-FN algorithm ensures the efficiency of the operation，and the modularity value of the community is increased from 0.756 to 0.806（the value of modularity is in the range［-0.5，1））.

The FC-FN algorithm has higher requirements on the accuracy and rationality of traffic flow contribution. Different traffic flow conditions will have different effects on traffic flow contribution and get different community divisions，so it can provide theoretical reference for flight season change and air route resource adjustment.

Future work is worth exploring in the following areas:

（1）Data aspect:Traffic flow data has an important impact on the calculation of traffic flow contribution. The method of judging the validity of data can be used as the research direction.

（2）Algorithm aspect:The number of iterations of the FC-FN algorithm is basically consistent with FN algorithm. Methods to reduce the number of iterations，improve the operation efficiency and the processing ability of the algorithm for massive data can be used as the research direction.