# Dynamic Control Subarea Division Based on Node Importance Evaluating

Authors: Xiujuan Tian; Chunyan Liang; Tianjun Feng
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

In order to optimize the existing control subarea division methods, a new dynamic subarea division method based on node importance evaluating is proposed for regional coordinated control. Firstly, considering the characteristics of road network and traffic flow between adjacent intersections, correlation degree model is established by calculating the correlation coefficients of traffic flow, signal cycle, and traffic state. Then, road traffic network is abstracted into a network topology structure graph. From the global perspective of the road network, intersection position information and the importance contribution between adjacent intersections are taken into account, and the correlation degrees between adjacent intersections are taken as the edge weights to construct intersection importance evaluation matrix. Finally, an actual road network is selected, and an improved Newman algorithm is employed to verify and analyze the method proposed in this paper. Results show that, compared with other methods, the control subarea division result of the new proposed method is more elaborate and more in line with the actual traffic flow characteristics. Moreover, dynamic subarea division can be realized according to the traffic characteristics of different periods, which can provide a good basis for the formulation of the signal control schemes in the next stage.


---

## Body

## 1. Introduction

The rapid development of cities leads to the continuous expansion of road network scale, frequent regional traffic congestion, and increasing difficulty in traffic management. As one of the effective means to solve various traffic problems, coordinated signal control has been developing and improving continuously. The premise of implementing coordinated control is to divide signal control subareas reasonably, and the result of signal control subarea division will directly affect the formulation of regional coordinated control strategy and the control operation.The concept of traffic control subarea was first proposed by Walinchus [1] in 1971, which laid a foundation for subsequent related studies. The basic idea is that the whole control area is divided into several reasonable subareas by means of correlation analysis, optimization theory, and advanced computer technology. The foundation of the division is the static spatial geometry characteristics and dynamic traffic flow characteristics of the road sections and the adjacent signalized intersections. The division results will provide the basis for the design of coordinated control schemes.In general, the methods of control subarea division can be divided into static subarea division and dynamic subarea division. The efficiency of coordinated control will be affected by static subarea division, because the subareas cannot be adjusted with the difference of traffic flow. With the development and improvement of real-time traffic detection methods, dynamic subarea division method has been becoming a research hotspot gradually.In recent years, there have been many researches in the field of dynamic control subarea division. Yagoda et al. [2] took the ratio of road traffic flow to road length as the index to measure the correlation degree between two adjacent intersections. Pinnell and Wilshire [3] considered the influence of traffic flow, road length, and vehicle arrival regularity at upstream intersection on the correlation degree. Taking the intersection flow ratio as the characteristic attribute, Jovanis and Moore [4] used the clustering analysis method to divide the control subareas. Li et al. [5] comprehensively took the influence of intersection spacing, discrete characteristics of traffic flow, traffic composition of arterial road, traffic flow, and signal cycle into consideration. And the influence coefficients of each factor were calculated, respectively. Finally, the fuzzy reasoning model of coordination coefficient was established, and control subareas were divided dynamically. By taking queuing vehicles, traffic flow, and cycle length into account, Lu et al. [6] studied the correlation degree models of two adjacent intersections and the combination of multiple intersections, respectively. Based on the correlation analysis, the subarea division method of coordinated control was put forward. Yang and Chen [7] proposed the periodic subarea and the phase difference/green ratio subarea. Dynamic subarea division method was studied.Comprehensively taking different factors such as traffic flow, signal cycle, and queue length into account, Liu and Zheng [8] used the principle of grey relational degree to divide control subareas of urban traffic network. Based on the spatial characteristics of traffic congestion in a specific period, Geroliminis et al. [9] introduced the concept of image segmentation. After the initial segmentation, a merging algorithm was developed. Besides, to make the division results more effective, a boundary adjustment algorithm was designed. Zhou et al. [10] focused on the physical characteristics and dynamic traffic information and took the weight of links in urban traffic network into consideration. Then, the optimized modularized fast network partitioning method was employed to identify the subareas of large urban traffic network.In order to make up for the inadequacy of traditional control subarea division methods in considering the complex characteristics of traffic network topology structure, Wang et al. [11] studied the optimization method of control subarea division. The new proposed method was based on agglomerated community discovery algorithm, which took community modularity as an index with the help of complex network theory. In view of the possible dimension disaster in the process of subarea division, Lu et al. [12] proposed a fast division method by combining dimension reduction processing and genetic algorithm. Shen and Yang [13] analyzed the influence of road distance, traffic flow density, and signal cycle on intersection relevance. And a subarea division method based on fuzzy algorithm was established.Based on Macroscopic Fundamental Diagram (MFD) theory, Lin et al. [14] designed a demand balance model. The traffic control subareas could be adjusted according to the actual traffic states in order to match the control strategy. So the whole road network could be optimized. Also based on MFD theory, Dong et al. [15] proposed a traffic control subarea division model and a key control area identification method. The model was closely combined with the dynamic traffic characteristics of road network, which effectively promoted the application of traffic control subarea division in the actual dynamic traffic control. Similarly, Xu et al. [16] proposed a new road network dynamic subarea division method based on different saturation for different states of intersections. Moreover, the correlation degree and similarity degree model among intersections in each subarea were established. By using spectral theory, road sections and intersections were divided into different subareas dynamically.For collecting and storing high-precision traffic data, Hu et al. [17] proposed a new vehicle detector layout method. On the strength of traffic state data, a correlation degree model of arterial road adjacent intersections was established. Considering the distance between adjacent intersections in the road network, traffic flow, travel time, discrete characteristics of traffic flow, signal cycle, traffic flow density, and other factors, Tian et al. [18] made a quantitative analysis of intersection correlation and established a correlation degree model for adjacent intersections. The traditional Newman algorithm was improved, and the regional road network was divided into dynamic subareas according to different traffic characteristics. And the method was verified.Summing up the researches, it is not difficult to find that the existing subarea division methods are mainly based on the similarity of traffic characteristics. By means of clustering analysis or other searching algorithms, the road sections and intersections with high similarity are divided into the same subarea. However, traffic network topology structure is not fully considered. Furthermore, most of the indicators are still based on distance, traffic flow, and signal cycle. As a consequence, the dynamic control subarea division method still needs to be improved.The main objective of this paper is to propose a new dynamic control subarea division method based on node importance evaluating, combined with improved Newman algorithm. The novelty of the proposed method is highlighted in the following aspects:(1)
The correlation degree model of adjacent intersections is established by adding traffic flow correlation coefficient, signal cycle correlation coefficient, and traffic state correlation coefficient together.(2)
Then, the intersection importance is evaluated by applying complex network theory, which takes the intersection position information and the importance contribution between adjacent intersections into consideration.(3)
Newman algorithm is improved by bringing in intersection importance and employed to verify and analyze the proposed method.(4)
An actual regional road network is selected to verify the effect and performance of the proposed method in this paper.The rest of this paper is organized as follows. Section2 formulates correlation degree of adjacent intersections by adding three correlation coefficients presented in Sections 2.1–2.3 together. In Section 3, the intersection importance is evaluated by applying complex network theory. In Section 4, the signal control subareas are divided by employing improved Newman algorithm, including the improving of Newman algorithm by bringing in intersection importance presented in Section 4.1 and the use presented in Section 4.2. In Section 5, the method proposed in this paper is verified by choosing an actual regional road network, including intersection importance contribution calculation presented in Section 5.1 and subarea division results analysis presented in Section 5.2. Section 6 reveals the conclusions and recommendations for future research.


## 2. Intersection Correlation Analysis

As it is known that the factors affecting the relevance of adjacent intersections mainly include the distance between adjacent intersections, traffic volume, signal timing parameters, and traffic states, the distance between the adjacent intersections is a static influencing factor, of which the influence degree on intersection relevance remains unchanged. Traffic volume, signal timing parameters, and traffic states are all dynamic influencing factors, of which the influence degree on the intersection correlation will change with the difference of traffic characteristics.Considering the dynamic and static factors comprehensively, the intersection correlation is quantitatively analyzed. And traffic flow correlation coefficient, signal cycle correlation coefficient, and traffic state correlation coefficient of adjacent intersections are calculated, respectively. Then, the correlation degree model of adjacent intersections is constructed, which provides the basis for control subarea division.


### 2.1. Traffic Flow Correlation Coefficient

When vehicles drive in the road sections between intersections, the fleet dispersion phenomenon often occurs. Therefore, the discrete characteristics of traffic flow should be taken into consideration when calculating the correlation degree between adjacent intersections. The classical Whitson correlation degree model [19] reflects the relationship between correlation degree, intersection distance, and traffic flow, but the influence of traffic flow discrete characteristics is not considered.Among the numerous discrete models of traffic flow, Pacey model [20, 21] and Robertson model [22] are the most widely used. Compared with Pacey model, Robertson model is simpler in calculation, which requires fewer parameters, and can describe the discrete phenomenon of traffic flow more accurately. The dispersion coefficient in Robertson model can be obtained from the following formula:(1)F=11+aT,where a is a constant. Studies show that when the value of a is between 0.1 and 0.15, it is more consistent with the actual traffic flow characteristics in China [23]. T is 0.8 times the average travel time of vehicles between the road sections.In addition, traffic flows on road sections between adjacent intersections are often bidirectional. So, directionality should be taken into account when calculating the correlation degree. Considering the discretization and directionality of traffic flow, the discretization coefficient is introduced to improve the Whitson correlation degree model. Then, the intersection flow correlation coefficient can be obtained, as shown in the following formula:(2)Iqi⟶j=0.51+aTi⟶jni⟶jqmaxi⟶j∑qi⟶j−1,where Iqi⟶j represents the traffic flow correlation coefficient between intersection i and j. Ti⟶j (min) indicates 0.8 times of the travel time ti⟶j between intersection i and j, which is equal to the ratio of intersection distance Li⟶j (m) to the average vehicle speed Vi⟶j. ni⟶j is the number of branches from the upstream intersection i to the downstream intersection j. For a typical intersection, ni⟶j is equal to 3. qmaxi⟶j (pcu/h) is the maximum traffic volume of branches from intersection i to intersection j. ∑qi⟶j (pcu/h) is the total traffic volume of the branch roads in the direction of intersection i to intersection j. And similarly, the inverse correlation can be calculated.Therefore, the traffic correlation coefficientIqi↔j between intersection i and intersection j is the larger value of Iqi⟶j and Iqj⟶i, as shown in the following formula:(3)Iqi↔j=maxIqi⟶j,Iqj⟶i.


### 2.2. Signal Cycle Correlation Coefficient

When adjacent intersections carry out coordinated control strategy, if the difference of signal cycle is too large, the vehicle delay at the intersection with small cycle time will increase. If the cycle time difference between intersections is small, it is easy to achieve better control effect. Therefore, the influence of cycle time should be considered in control subareas division.Based on the existing research [24], the signal cycle correlation coefficient of adjacent intersections is defined as (4)ICi,j=2R−1×minR+12−maxCi,CjminCi,Cj,0.5,where ICi,j represents the signal cycle correlation coefficient, of which the value is between 0 and 1. Ci and Cj are the cycle times of intersections i and j, respectively. R represents the maximum possible value of signal control cycle ratio at adjacent intersections, of which the value is usually 2. maxCi,Cj is the larger cycle time of the two adjacent intersections, and minCi,Cj is the smaller cycle time of the two adjacent intersections.


### 2.3. Traffic State Correlation Coefficient

In order to make the road sections and intersections with similar traffic state be divided into the same control subarea as far as possible, the traffic state of the road sections should be considered when the subarea is divided. The traffic flow density can directly reflect the congestion degree and the traffic state of the road. Based on the existing research, the correlation coefficientIρi↔j model [24] of road traffic state can be established:(5)Iρi↔j=minmaxρi⟶jρsi⟶j,ρj⟶iρsj⟶i,1,(6)ρi⟶j=∑qi⟶jNi⟶j∗Li⟶j,where Iρi↔j denotes traffic state correlation coefficient of road section between intersection i and intersection j. And the value of Iρi↔j is between 0 and 1. ρi⟶j (pcu/m) represents the traffic flow density of the road section from intersection i to intersection j, which can be calculated by formula (6). ρsj⟶i (pcu/m) is the traffic flow density of saturation state in the road section from intersection i to intersection j. Ni⟶j is the number of lanes on the road section in the corresponding direction.To sum up, the correlation degreeIij of adjacent intersections can be obtained by comprehensively considering the traffic flow correlation coefficient, signal cycle correlation coefficient, and road traffic state correlation coefficient and adding them together, as shown in the following formula:(7)Iij=αIqi↔j+βICi,j+γIρi↔j,where Iqi↔j represents the traffic flow correlation coefficient between intersection i and intersection j, which can be obtained by formula (3). ICi,j is signal cycle correlation coefficient, which can be obtained by formula (4). Iρi↔j denotes road traffic state correlation coefficient, which can be calculated by formulas (5) and (6). α, β, and γ are the weight coefficients of the three correlation coefficients, respectively, of which the values are determined by entropy weight method [25]. Entropy was originally a thermodynamic concept, which was first introduced into information theory and called as information entropy by Shannon [25] in 1948. At present, it has been widely used in engineering technology, social economy, and other fields. The basic idea of entropy weight method is to determine the objective weight according to the index variability. Generally speaking, the smaller the information entropy of an index is, the greater its weight will be. On the contrary, the greater the information entropy of an index, the smaller the weight.


## 2.1. Traffic Flow Correlation Coefficient

When vehicles drive in the road sections between intersections, the fleet dispersion phenomenon often occurs. Therefore, the discrete characteristics of traffic flow should be taken into consideration when calculating the correlation degree between adjacent intersections. The classical Whitson correlation degree model [19] reflects the relationship between correlation degree, intersection distance, and traffic flow, but the influence of traffic flow discrete characteristics is not considered.Among the numerous discrete models of traffic flow, Pacey model [20, 21] and Robertson model [22] are the most widely used. Compared with Pacey model, Robertson model is simpler in calculation, which requires fewer parameters, and can describe the discrete phenomenon of traffic flow more accurately. The dispersion coefficient in Robertson model can be obtained from the following formula:(1)F=11+aT,where a is a constant. Studies show that when the value of a is between 0.1 and 0.15, it is more consistent with the actual traffic flow characteristics in China [23]. T is 0.8 times the average travel time of vehicles between the road sections.In addition, traffic flows on road sections between adjacent intersections are often bidirectional. So, directionality should be taken into account when calculating the correlation degree. Considering the discretization and directionality of traffic flow, the discretization coefficient is introduced to improve the Whitson correlation degree model. Then, the intersection flow correlation coefficient can be obtained, as shown in the following formula:(2)Iqi⟶j=0.51+aTi⟶jni⟶jqmaxi⟶j∑qi⟶j−1,where Iqi⟶j represents the traffic flow correlation coefficient between intersection i and j. Ti⟶j (min) indicates 0.8 times of the travel time ti⟶j between intersection i and j, which is equal to the ratio of intersection distance Li⟶j (m) to the average vehicle speed Vi⟶j. ni⟶j is the number of branches from the upstream intersection i to the downstream intersection j. For a typical intersection, ni⟶j is equal to 3. qmaxi⟶j (pcu/h) is the maximum traffic volume of branches from intersection i to intersection j. ∑qi⟶j (pcu/h) is the total traffic volume of the branch roads in the direction of intersection i to intersection j. And similarly, the inverse correlation can be calculated.Therefore, the traffic correlation coefficientIqi↔j between intersection i and intersection j is the larger value of Iqi⟶j and Iqj⟶i, as shown in the following formula:(3)Iqi↔j=maxIqi⟶j,Iqj⟶i.


## 2.2. Signal Cycle Correlation Coefficient

When adjacent intersections carry out coordinated control strategy, if the difference of signal cycle is too large, the vehicle delay at the intersection with small cycle time will increase. If the cycle time difference between intersections is small, it is easy to achieve better control effect. Therefore, the influence of cycle time should be considered in control subareas division.Based on the existing research [24], the signal cycle correlation coefficient of adjacent intersections is defined as (4)ICi,j=2R−1×minR+12−maxCi,CjminCi,Cj,0.5,where ICi,j represents the signal cycle correlation coefficient, of which the value is between 0 and 1. Ci and Cj are the cycle times of intersections i and j, respectively. R represents the maximum possible value of signal control cycle ratio at adjacent intersections, of which the value is usually 2. maxCi,Cj is the larger cycle time of the two adjacent intersections, and minCi,Cj is the smaller cycle time of the two adjacent intersections.


## 2.3. Traffic State Correlation Coefficient

In order to make the road sections and intersections with similar traffic state be divided into the same control subarea as far as possible, the traffic state of the road sections should be considered when the subarea is divided. The traffic flow density can directly reflect the congestion degree and the traffic state of the road. Based on the existing research, the correlation coefficientIρi↔j model [24] of road traffic state can be established:(5)Iρi↔j=minmaxρi⟶jρsi⟶j,ρj⟶iρsj⟶i,1,(6)ρi⟶j=∑qi⟶jNi⟶j∗Li⟶j,where Iρi↔j denotes traffic state correlation coefficient of road section between intersection i and intersection j. And the value of Iρi↔j is between 0 and 1. ρi⟶j (pcu/m) represents the traffic flow density of the road section from intersection i to intersection j, which can be calculated by formula (6). ρsj⟶i (pcu/m) is the traffic flow density of saturation state in the road section from intersection i to intersection j. Ni⟶j is the number of lanes on the road section in the corresponding direction.To sum up, the correlation degreeIij of adjacent intersections can be obtained by comprehensively considering the traffic flow correlation coefficient, signal cycle correlation coefficient, and road traffic state correlation coefficient and adding them together, as shown in the following formula:(7)Iij=αIqi↔j+βICi,j+γIρi↔j,where Iqi↔j represents the traffic flow correlation coefficient between intersection i and intersection j, which can be obtained by formula (3). ICi,j is signal cycle correlation coefficient, which can be obtained by formula (4). Iρi↔j denotes road traffic state correlation coefficient, which can be calculated by formulas (5) and (6). α, β, and γ are the weight coefficients of the three correlation coefficients, respectively, of which the values are determined by entropy weight method [25]. Entropy was originally a thermodynamic concept, which was first introduced into information theory and called as information entropy by Shannon [25] in 1948. At present, it has been widely used in engineering technology, social economy, and other fields. The basic idea of entropy weight method is to determine the objective weight according to the index variability. Generally speaking, the smaller the information entropy of an index is, the greater its weight will be. On the contrary, the greater the information entropy of an index, the smaller the weight.


## 3. Intersection Importance Evaluation

Using the idea of graph theory, the intersections in the urban road traffic network can be abstracted as points, and the road sections between adjacent intersections can be abstracted as edges. Then, the road network can be abstracted as the network topology structure graph composed of nodes and edges. Therefore, the importance evaluation of intersections can be transformed into importance evaluation of nodes in complex networks.The difference of intersection location and adjacent intersections will lead to the difference of the intersections importance in road traffic network. Moreover, intersections importance will be affected by adjacent intersections. Therefore, when evaluating the importance degree of complex network nodes, both node location (global importance) and importance degree contribution of neighboring nodes (local importance) should be taken into comprehensive consideration [26]. The same idea to evaluate intersection importance is also adopted in this paper.Similar to other complex networks, there is no importance dependence between isolated intersections. Road network adjacency matrix can directly reflect the adjacent situation between intersections. So, the importance contribution relationship between intersections can also be obtained through the mapping of the network adjacency matrix.It is well known that the traffic flow in a road network has obvious periodicity and fluctuation. Consequently, different from other networks, the elements in the road traffic network graph are not simply Boolean relations. Therefore, the road traffic network can be abstracted as a weighted connected networkG=V,E,W, where V denotes the node set, and E denotes the edge set. A pair of points in node set V correspond to an edge in edge set E. W denotes the network edge weights set. Considering the correlation between adjacent intersections, the correlation degree Iij between intersection i and intersection j is taken as the weight of the connection edge to construct intersection importance evaluation matrix.Let the node set beV=v1,v2,…,vn, and let vi,vj represent the edge between node vi and node vj. Then, the edge set can be represented by E⊂vi,vj:vi,vj∈V. Degree Di of node vi represents the number of nodes adjacent to node vi.Referring to the existing researches [26, 27], in an nonlooped undirected network with n nodes and an average degree of k, node vi contributes Di/k2 of its importance to every node adjacent to it. The importance contribution proportion matrix of all nodes in the network to their neighboring nodes is defined as the importance contribution matrix of nodes, denoted by HIC, as shown in the following formula:(8)HIC=1w12r12D2k2⋯w1nr1nDnk2w21r21D1k21⋯w2nr2nDnk2⋮⋮⋯⋮wn1rn1D1k2wn2rn2D2k2⋯1,where wij is the elements in edge weight matrix W of the given network, which represents the weight of the edge between node vi and node vj, and is equal to the correlation degree value between intersections. The bigger the value, the greater the importance contribution value between the two nodes. rij is the elements in adjacency matrix Rij of the given network, with a value of 0 or 1. When node vi is directly connected to node vj, rij is 1; otherwise, it is 0. The elements in matrix HIC are the importance contribution ratios of node vi to adjacent nodes. The diagonal element is 1, indicating that the proportion of the node importance contribution to itself is 1. The node importance contribution matrix HIC has the same structure as the network adjacency matrix Rij, and the following mapping relationship exists:(9)rij⟶rijDjk2,i≠j,rij⟶1,i=j.Referring to the existing research results [26], in order to reflect the role of intersections in the road network, the utility of intersections is defined, which is equal to the average correlation degree value of intersections and is expressed as (10)Vi=1n∑j=1,j≠inIij,where n is the intersections number of the network, and Iij is the correlation degree value between intersection i and intersection j. From the definition of Vi, it is not difficult to see that the utility of an intersection expresses the association of the intersection in the whole road network and reflects the contribution of the intersection to the traffic transmission of the road network. Therefore, the greater the utility value of an intersection, the more important the location of the intersection in the road network. Therefore, the utility of the intersection can reflect the importance of the intersection to some extent.The importance of the intersection depends on the intersection location and the adjacent relationship between the intersections. Therefore, in this paper, the degree is used to represent the importance degree correlation between intersections, and the intersection utility is used to represent location information. Consequently, the intersection importance evaluation matrixHE can be obtained as (11)HE=V1I12r12D2V2k2⋯I1nr1nDnVnk2I21r21D1V1k2V2⋯I2nr2nDnVnk2⋮⋮⋯⋮In1rn1D1V1k2In2rn2D2V2k2⋯Vn,where HEij represents the importance contribution value of intersection j to intersection i. It is not difficult to see that the importance contribution value of an intersection to its adjacent nodes is related to its utility and degree value. The greater the utility value and degree value are, the greater the importance contribution value will be.


## 4. Control Subarea Division Based on Improved Newman Algorithm

Considering the relevance of adjacent intersections in the road network, a new control subarea division algorithm is proposed by bringing edge weight between nodei and node j into the classical Newman community algorithm.


### 4.1. Newman Algorithm Improvement

Newman fast algorithm is a community rapid aggregation algorithm, which was put forward by Newman [28, 29] in 2004 based on GN algorithm [30]. Based on the idea of greedy algorithm, each node in the community is regarded as a separate community at the initial division stage. And then, each node is merged according to certain rules, so as to realize the division of community structure.In order to make the Newman algorithm more suitable for weighted network partition, the traditional Newman algorithm is improved based on the existing research [31].Firstly, the modularity calculation formula is improved. Assume that a network contains a total ofn communities, denoted by c1,c2,…,cn. Define n-dimensional symmetric matrix c=cij. Matrix element cij is equal to the sum of the edge weights of community i and community j, representing the ratio of the internal edge weights of the community to the edge weights of the network. vi=∑jcij is the sum of elements in each row of matrix c, representing the ratio of connecting edge weights of internal and external nodes of community i to network edge weights. C2 is the sum of all the entries in C2.Therefore, the improved modularityQw can be obtained, as shown in (12)Qw=∑icii−vi2=Tre−C2.Since the improved algorithm takes the edge weight into account, which includes the relevance of intersections, the improved algorithm also takes the relevance of network nodes into account. The elementseij in the matrix E are improved, as shown in (13)eij=wij2∗∑i,jwij,edgevi,vjexists,0,ortherwise,where wij represents the weight of the edge connecting node i to node j. Then, ai can be calculated by(14)ai=∑jwij2∗∑i,jwij.In the process of association merger, the value ofΔQ needs to be recalculated. The merging principle is the same as Newman algorithm, which is along the direction, where Q increases the most or decreases the least. After each merge, the values of eij and ai need to be recalculated, and the rows and columns associated with communities i and j need to be added. The community is constantly merged until all nodes are merged into a community, and the algorithm ends. The tree graph of community division is output, and the community division when the Q value reaches the maximum is selected as the final division result.


### 4.2. Dynamic Subarea Division Process

Many researches have shown that road traffic network is a typical complex network, and it is feasible and advantageous to dynamic control subarea division by combining community partitioning algorithm in complex network. According to the improved Newman algorithm, traffic control subareas are divided, and the steps are as follows:Step 1. Simplify the given traffic network by abstracting intersections as nodes and road sections between intersections as edges.Step 2. Label the nodes and edges in the simplified network graph.Step 3. Collect and process the traffic information of nodes and edges in the network, and then substitute it into the relational degree model to get the evaluation matrix of intersection importance degree.Step 4. Initial division of the traffic network is made, and each node is an independent community.Step 5. Define and initialize the sum of all elements in the auxiliary matrixE and array A, as shown in formulae (13) and (14).Step 6. Merge the node pairs connected by edges and calculate the update modularity incrementΔQ, as shown in formula (10).Step 7. Select the node with the largest increment of modularityΔQ to merge and update elements eij.Step 8. Go to Step 6 and continue until the entire network is merged into a community.Step 9. At the end of the algorithm, output the tree graph of control subareas.Step 10. Select the division result when the module degreeQ value is the maximum as the optimal result of the signal control subarea division.


## 4.1. Newman Algorithm Improvement

Newman fast algorithm is a community rapid aggregation algorithm, which was put forward by Newman [28, 29] in 2004 based on GN algorithm [30]. Based on the idea of greedy algorithm, each node in the community is regarded as a separate community at the initial division stage. And then, each node is merged according to certain rules, so as to realize the division of community structure.In order to make the Newman algorithm more suitable for weighted network partition, the traditional Newman algorithm is improved based on the existing research [31].Firstly, the modularity calculation formula is improved. Assume that a network contains a total ofn communities, denoted by c1,c2,…,cn. Define n-dimensional symmetric matrix c=cij. Matrix element cij is equal to the sum of the edge weights of community i and community j, representing the ratio of the internal edge weights of the community to the edge weights of the network. vi=∑jcij is the sum of elements in each row of matrix c, representing the ratio of connecting edge weights of internal and external nodes of community i to network edge weights. C2 is the sum of all the entries in C2.Therefore, the improved modularityQw can be obtained, as shown in (12)Qw=∑icii−vi2=Tre−C2.Since the improved algorithm takes the edge weight into account, which includes the relevance of intersections, the improved algorithm also takes the relevance of network nodes into account. The elementseij in the matrix E are improved, as shown in (13)eij=wij2∗∑i,jwij,edgevi,vjexists,0,ortherwise,where wij represents the weight of the edge connecting node i to node j. Then, ai can be calculated by(14)ai=∑jwij2∗∑i,jwij.In the process of association merger, the value ofΔQ needs to be recalculated. The merging principle is the same as Newman algorithm, which is along the direction, where Q increases the most or decreases the least. After each merge, the values of eij and ai need to be recalculated, and the rows and columns associated with communities i and j need to be added. The community is constantly merged until all nodes are merged into a community, and the algorithm ends. The tree graph of community division is output, and the community division when the Q value reaches the maximum is selected as the final division result.


## 4.2. Dynamic Subarea Division Process

Many researches have shown that road traffic network is a typical complex network, and it is feasible and advantageous to dynamic control subarea division by combining community partitioning algorithm in complex network. According to the improved Newman algorithm, traffic control subareas are divided, and the steps are as follows:Step 1. Simplify the given traffic network by abstracting intersections as nodes and road sections between intersections as edges.Step 2. Label the nodes and edges in the simplified network graph.Step 3. Collect and process the traffic information of nodes and edges in the network, and then substitute it into the relational degree model to get the evaluation matrix of intersection importance degree.Step 4. Initial division of the traffic network is made, and each node is an independent community.Step 5. Define and initialize the sum of all elements in the auxiliary matrixE and array A, as shown in formulae (13) and (14).Step 6. Merge the node pairs connected by edges and calculate the update modularity incrementΔQ, as shown in formula (10).Step 7. Select the node with the largest increment of modularityΔQ to merge and update elements eij.Step 8. Go to Step 6 and continue until the entire network is merged into a community.Step 9. At the end of the algorithm, output the tree graph of control subareas.Step 10. Select the division result when the module degreeQ value is the maximum as the optimal result of the signal control subarea division.


## 5. Model Verification

In order to verify the validity of the model in this paper, a regional road network is selected for model verification. Relevant data and information of traffic flow data are derived from OpenITS open data network (https://www.openits.cn/openData2/index.jhtml). The road network includes 19 signal-controlled intersections and 46 road sections.For the convenience of intuitiveness and subarea division, the road network is simplified. Signal control intersections are abstracted as nodes, and road sections are abstracted as edges. The nodes and edges are numbered respectively to get a simplified road network graph. Combined with Baidu Map, the distance between each intersection and the number of lanes can be obtained. The distance between adjacent nodes is indicated in Figure1.Figure 1
Simplified regional road network graph for subarea division validation.


### 5.1. Intersection Importance Contribution Calculation

Based on the network open data, traffic flow detection data from 8 : 00-9:00 was selected for model verification and analysis. First of all, traffic flow information and travel time were counted, and flow correlation coefficient, signal cycle correlation coefficient, and road state correlation coefficient were calculated, respectively. The related parameters for correlation degree calculation are shown in Table1.Table 1
Related parameters for correlation degree calculation.
Parameteri→jni→jnj→iti→jtj→iqmaxi→jqmaxj→i∑qi→j∑qj→iNi↔j1-2331.2672.11717219140128221–5331.7331.81725852873567532-3321.5831.11716724041728313-4231.4333.43323626764347414-5321.3336.40021619546234034–7331.8173.43323427460254915-6221.7671.050473557108076636-7231.6504.00028421441753916–13231.4501.50051540067671337-8332.1172.10018920338941717–12321.0831.30028324955640418-9331.5001.23323517360870918–11331.9501.68319819744847629-10331.9331.933297237435612110-11332.3672.250196296499398210–17322.1671.950195230417362111-12321.2171.417198183406400211–16331.5671.917188228277577212–15231.6001.500390235694495114-15331.5831.667438493667538214–19331.9832.467398296758546315-16331.0832.167432454587592216-17321.4831.683410421697915216–19332.0001.533228167496339218-19231.3331.5505125658466983Then, weight coefficients of the three correlation coefficientsα=0.356, β=0.306, and γ=0.338 could be obtained by entropy weight method through MATLAB software. Based on the numerical relationship between weight parameters α, β and γ, it is not difficult to find that flow correlation coefficient, signal cycle correlation coefficient, and road state correlation coefficient were of the same importance to the correlation degree of adjacent intersections.In order to reduce the subarea division error caused by data processing, the three weight coefficientsα, β and γ were approximated to 1 for the given network. In other words, the correlation degree Iij could be calculated by formula Iij=Iqi↔j+ICi,j+Iρi↔j, of which the values are shown in Table 2.Table 2
The correlation degreeIij for adjacent intersections.
i−jIiji−jIij1–20.7729–101.5951–50.72910–111.3912–30.67110–171.3363–41.61211–120.4784–50.92011–161.6114–70.61312–150.8875–60.88314–151.1366–71.41314–191.2086–131.43315–161.5637–80.57716–171.4717–121.24916–190.5118–90.98718–190.8858–110.716——Then, the intersection importance evaluation matrixHE could be obtained by formula (11). The importance contribution HEij of adjacent intersections is shown in Table 3. The values of HEij, which are not shown in Table 3, are all zero.Table 3
The importance contributionHEij of adjacent intersections.
i,jHEiji,jHEiji,jHEiji,jHEiji,jHEiji,jHEij(1, 2)0.005(9, 10)0.060(2, 1)0.006(10, 9)0.027(1, 1)0.028(14, 14)0.053(1, 5)0.017(10, 11)0.087(5, 1)0.006(11, 10)0.052(2, 2)0.022(15, 15)0.058(2, 3)0.009(10, 17)0.029(3, 2)0.004(17, 10)0.050(3, 3)0.047(16, 16)0.119(3, 4)0.045(11, 12)0.015(4, 3)0.022(12, 11)0.030(4, 4)0.064(17, 17)0.075(4, 5)0.021(11, 16)0.110(5, 4)0.026(16, 11)0.100(5, 5)0.052(18, 18)0.020(4, 7)0.031(12, 15)0.022(7, 4)0.017(15, 12)0.028(6, 6)0.074(19, 19)0.041(5, 6)0.028(14, 15)0.029(6, 5)0.020(15, 14)0.018(7, 7)0.088——(6, 7)0.072(14, 19)0.021(7, 6)0.045(19, 14)0.019(8, 8)0.054——(6, 13)0.007(15, 16)0.107(13, 6)0.046(16, 15)0.039(9, 9)0.059——(7, 8)0.014(16, 17)0.032(8, 7)0.029(17, 16)0.101(10, 10)0.087——(7, 12)0.039(16, 19)0.009(12, 7)0.063(19, 16)0.035(11, 11)0.108——(8, 9)0.017(18, 19)0.016(9, 8)0.023(19, 18)0.003(12, 12)0.073——(8, 11)0.045——(11, 8)0.017——(13, 13)0.033——


### 5.2. Subarea Division Results Analysis

In order to verify the effectiveness of the proposed method, the improved Newman algorithm is used to divide the subareas of regional road network.Firstly, without considering the importance of road network nodes, the intersection relational degree matrix is taken as the input data to divide the control subareas using improved Newman algorithm. The results are shown in Figure2. During the algorithm execution, the module degree value Q corresponding to each merging process is shown in Figure 3.Figure 2
Traffic subarea division results considering correlation degree based on improved Newman algorithm.Figure 3
Modular values of subarea division results considering correlation degree based on improved Newman algorithm.Then, considering the importance of intersections, the importance evaluation matrix of intersections is introduced, and improved Newman algorithm is used to divide the verification network into subareas. The results are shown in Figure4. In the process of subarea merging, the change curve of modularity Q value is shown in Figure 5.Figure 4
Traffic subarea division results considering node importance based on improved Newman algorithm.Figure 5
Modular values of subarea division results considering node importance based on improved Newman algorithm.It can be seen from Figure3 that, for the subarea division considering the correlation degree based on the improved Newman algorithm, when the subareas are combined to the number 34, the modular degree Q reaches the maximum value of 0.5015. At this time, the subarea division result is optimal, verifying that the regional road network is divided into four control subareas. According to the subarea division tree graph in Figure 2, it can be seen that intersections 1, 2, 3, 4, and 5 are in control subarea 1. Intersections 6, 7, 12, and 13 are in control subarea 2. Intersections 8, 9, 10, and 11 are in control subarea 3, and intersections 14, 15, 16, 17, 18, and 19 are in control subarea 4.In addition, it can be seen from Figure5 that, in the division of the improved Newman algorithm considering the importance of nodes, when the subareas are merged to the number 33, the modular degree Q reaches the maximum value of 0.5582. At this time, the subarea division result is optimal, verifying that the road network is divided into five control subareas. According to the tree graph of subareas in Figure 4, at this time, intersections 15, 16, and 17 are in the same control subarea. Intersections 14, 18, and 19 are in a control subarea. Intersections 8, 9, and 10 are in a control subarea. Intersections 1, 2, 3, 4, and 5 are in a control subarea. And intersections 6, 7, 12, and 13 are in the same control subarea.In order to show and compare the subarea divisions of regional road network by the two algorithms more intuitively, the subarea composition graph is drawn, respectively. Figure6 shows the traffic control subarea composition of improved Newman algorithm considering correlation degree. And Figure 7 shows the traffic control subarea composition of improved Newman algorithm considering node importance degree proposed in this paper.Figure 6
Traffic control subarea composition considering correlation degree based on improved Newman algorithm.Figure 7
Traffic control subarea composition considering node importance based on improved Newman algorithm.From the subarea division results of the two methods in Figures6 and 7, compared with the method using the improved Newman algorithm considering correlation degree, the method proposed in this paper, which considers node importance based on improved Newman algorithm, can divide dynamic subareas in more detail, and the results are more consistent with the actual traffic characteristics.Besides, the subareas can be divided dynamically according to the traffic characteristics of different periods. This is because, in the process of subarea division, Newman algorithm does not consider the correlation characteristics between adjacent intersections, and the influence of the distance and flow between intersections on the subarea division results, which only takes the correlation matrix between intersections as the input of the model. However, for a given road network, the correlation matrix is fixed, so the subarea division results are also fixed and cannot change with the change of traffic characteristics [18].Different from Newman algorithm, the two verification methods adopted in this paper both use improved Newman algorithm, which introduces the correlation degree or node importance degree between intersections and fully takes the traffic characteristics into account. Therefore, the subarea results will change with the change of traffic characteristics, and both of them can realize the dynamic division of control subareas.Besides, the algorithm proposed in this paper not only considers the relevance degree of adjacent intersections, but also takes the location information of nodes and the global characteristics of the road network into consideration to establish the evaluation matrix of intersection importance. The influencing factors are more comprehensive and closer to the actual state of the road network.In conclusion, the model proposed in this paper performs best. Therefore, the effectiveness of the proposed method is proved.


## 5.1. Intersection Importance Contribution Calculation

Based on the network open data, traffic flow detection data from 8 : 00-9:00 was selected for model verification and analysis. First of all, traffic flow information and travel time were counted, and flow correlation coefficient, signal cycle correlation coefficient, and road state correlation coefficient were calculated, respectively. The related parameters for correlation degree calculation are shown in Table1.Table 1
Related parameters for correlation degree calculation.
Parameteri→jni→jnj→iti→jtj→iqmaxi→jqmaxj→i∑qi→j∑qj→iNi↔j1-2331.2672.11717219140128221–5331.7331.81725852873567532-3321.5831.11716724041728313-4231.4333.43323626764347414-5321.3336.40021619546234034–7331.8173.43323427460254915-6221.7671.050473557108076636-7231.6504.00028421441753916–13231.4501.50051540067671337-8332.1172.10018920338941717–12321.0831.30028324955640418-9331.5001.23323517360870918–11331.9501.68319819744847629-10331.9331.933297237435612110-11332.3672.250196296499398210–17322.1671.950195230417362111-12321.2171.417198183406400211–16331.5671.917188228277577212–15231.6001.500390235694495114-15331.5831.667438493667538214–19331.9832.467398296758546315-16331.0832.167432454587592216-17321.4831.683410421697915216–19332.0001.533228167496339218-19231.3331.5505125658466983Then, weight coefficients of the three correlation coefficientsα=0.356, β=0.306, and γ=0.338 could be obtained by entropy weight method through MATLAB software. Based on the numerical relationship between weight parameters α, β and γ, it is not difficult to find that flow correlation coefficient, signal cycle correlation coefficient, and road state correlation coefficient were of the same importance to the correlation degree of adjacent intersections.In order to reduce the subarea division error caused by data processing, the three weight coefficientsα, β and γ were approximated to 1 for the given network. In other words, the correlation degree Iij could be calculated by formula Iij=Iqi↔j+ICi,j+Iρi↔j, of which the values are shown in Table 2.Table 2
The correlation degreeIij for adjacent intersections.
i−jIiji−jIij1–20.7729–101.5951–50.72910–111.3912–30.67110–171.3363–41.61211–120.4784–50.92011–161.6114–70.61312–150.8875–60.88314–151.1366–71.41314–191.2086–131.43315–161.5637–80.57716–171.4717–121.24916–190.5118–90.98718–190.8858–110.716——Then, the intersection importance evaluation matrixHE could be obtained by formula (11). The importance contribution HEij of adjacent intersections is shown in Table 3. The values of HEij, which are not shown in Table 3, are all zero.Table 3
The importance contributionHEij of adjacent intersections.
i,jHEiji,jHEiji,jHEiji,jHEiji,jHEiji,jHEij(1, 2)0.005(9, 10)0.060(2, 1)0.006(10, 9)0.027(1, 1)0.028(14, 14)0.053(1, 5)0.017(10, 11)0.087(5, 1)0.006(11, 10)0.052(2, 2)0.022(15, 15)0.058(2, 3)0.009(10, 17)0.029(3, 2)0.004(17, 10)0.050(3, 3)0.047(16, 16)0.119(3, 4)0.045(11, 12)0.015(4, 3)0.022(12, 11)0.030(4, 4)0.064(17, 17)0.075(4, 5)0.021(11, 16)0.110(5, 4)0.026(16, 11)0.100(5, 5)0.052(18, 18)0.020(4, 7)0.031(12, 15)0.022(7, 4)0.017(15, 12)0.028(6, 6)0.074(19, 19)0.041(5, 6)0.028(14, 15)0.029(6, 5)0.020(15, 14)0.018(7, 7)0.088——(6, 7)0.072(14, 19)0.021(7, 6)0.045(19, 14)0.019(8, 8)0.054——(6, 13)0.007(15, 16)0.107(13, 6)0.046(16, 15)0.039(9, 9)0.059——(7, 8)0.014(16, 17)0.032(8, 7)0.029(17, 16)0.101(10, 10)0.087——(7, 12)0.039(16, 19)0.009(12, 7)0.063(19, 16)0.035(11, 11)0.108——(8, 9)0.017(18, 19)0.016(9, 8)0.023(19, 18)0.003(12, 12)0.073——(8, 11)0.045——(11, 8)0.017——(13, 13)0.033——


## 5.2. Subarea Division Results Analysis

In order to verify the effectiveness of the proposed method, the improved Newman algorithm is used to divide the subareas of regional road network.Firstly, without considering the importance of road network nodes, the intersection relational degree matrix is taken as the input data to divide the control subareas using improved Newman algorithm. The results are shown in Figure2. During the algorithm execution, the module degree value Q corresponding to each merging process is shown in Figure 3.Figure 2
Traffic subarea division results considering correlation degree based on improved Newman algorithm.Figure 3
Modular values of subarea division results considering correlation degree based on improved Newman algorithm.Then, considering the importance of intersections, the importance evaluation matrix of intersections is introduced, and improved Newman algorithm is used to divide the verification network into subareas. The results are shown in Figure4. In the process of subarea merging, the change curve of modularity Q value is shown in Figure 5.Figure 4
Traffic subarea division results considering node importance based on improved Newman algorithm.Figure 5
Modular values of subarea division results considering node importance based on improved Newman algorithm.It can be seen from Figure3 that, for the subarea division considering the correlation degree based on the improved Newman algorithm, when the subareas are combined to the number 34, the modular degree Q reaches the maximum value of 0.5015. At this time, the subarea division result is optimal, verifying that the regional road network is divided into four control subareas. According to the subarea division tree graph in Figure 2, it can be seen that intersections 1, 2, 3, 4, and 5 are in control subarea 1. Intersections 6, 7, 12, and 13 are in control subarea 2. Intersections 8, 9, 10, and 11 are in control subarea 3, and intersections 14, 15, 16, 17, 18, and 19 are in control subarea 4.In addition, it can be seen from Figure5 that, in the division of the improved Newman algorithm considering the importance of nodes, when the subareas are merged to the number 33, the modular degree Q reaches the maximum value of 0.5582. At this time, the subarea division result is optimal, verifying that the road network is divided into five control subareas. According to the tree graph of subareas in Figure 4, at this time, intersections 15, 16, and 17 are in the same control subarea. Intersections 14, 18, and 19 are in a control subarea. Intersections 8, 9, and 10 are in a control subarea. Intersections 1, 2, 3, 4, and 5 are in a control subarea. And intersections 6, 7, 12, and 13 are in the same control subarea.In order to show and compare the subarea divisions of regional road network by the two algorithms more intuitively, the subarea composition graph is drawn, respectively. Figure6 shows the traffic control subarea composition of improved Newman algorithm considering correlation degree. And Figure 7 shows the traffic control subarea composition of improved Newman algorithm considering node importance degree proposed in this paper.Figure 6
Traffic control subarea composition considering correlation degree based on improved Newman algorithm.Figure 7
Traffic control subarea composition considering node importance based on improved Newman algorithm.From the subarea division results of the two methods in Figures6 and 7, compared with the method using the improved Newman algorithm considering correlation degree, the method proposed in this paper, which considers node importance based on improved Newman algorithm, can divide dynamic subareas in more detail, and the results are more consistent with the actual traffic characteristics.Besides, the subareas can be divided dynamically according to the traffic characteristics of different periods. This is because, in the process of subarea division, Newman algorithm does not consider the correlation characteristics between adjacent intersections, and the influence of the distance and flow between intersections on the subarea division results, which only takes the correlation matrix between intersections as the input of the model. However, for a given road network, the correlation matrix is fixed, so the subarea division results are also fixed and cannot change with the change of traffic characteristics [18].Different from Newman algorithm, the two verification methods adopted in this paper both use improved Newman algorithm, which introduces the correlation degree or node importance degree between intersections and fully takes the traffic characteristics into account. Therefore, the subarea results will change with the change of traffic characteristics, and both of them can realize the dynamic division of control subareas.Besides, the algorithm proposed in this paper not only considers the relevance degree of adjacent intersections, but also takes the location information of nodes and the global characteristics of the road network into consideration to establish the evaluation matrix of intersection importance. The influencing factors are more comprehensive and closer to the actual state of the road network.In conclusion, the model proposed in this paper performs best. Therefore, the effectiveness of the proposed method is proved.


## 6. Conclusions

Focused on optimizing control subarea division methods, a new dynamic control subarea division method based on node importance evaluating is put forward in this paper.Considering the characteristics of road network and traffic flow, the intersection correlation degree model is built by calculating the correlation coefficients of traffic flow, signal cycle, and traffic state for adjacent intersections. Then, the road traffic network is abstracted into the network topology structure graph. From the global perspective of the road network, the intersection position information and the importance contribution between adjacent intersections are taken into account. The correlation degree between adjacent intersections is taken as the edge weight to construct the intersection importance evaluation matrix. Finally, an actual road network is selected. The intersection importance is introduced into the Newman fast partition algorithm, which is improved. Then, the improved Newman algorithm is employed to verify and analyze the performance of the proposed model.The subdivision results show that the model proposed in this paper can divide the control subareas in more detail and more in line with the actual traffic flow characteristics. Moreover, dynamic subdivision can be realized according to the traffic characteristics of different periods, which can provide a good foundation for the formulation of signal control schemes. Then, the effectiveness of the method in this paper is proved.This paper only considers the relevance of adjacent intersections but does not consider the relevance between different intersections in the road network. In addition, the dynamic subdivision method under supersaturation is not researched. Due to the limitation of experimental conditions, the model verification in this paper is only conducted for one traffic state. Therefore, it is advisable to establish the correlation degree model between different intersections in the future research. Moreover, the study will be carried out for oversaturated traffic state with more field data collection efforts. Model verification will be carried out for traffic flow data with different periodic characteristics, and the coordination control method between subareas will be researched.



---

*Source: 9923514-2021-08-18.xml*