Limits...
Structural controllability of complex networks based on preferential matching.

Zhang X, Lv T, Yang X, Zhang B - PLoS ONE (2014)

Bottom Line: Therefore, past research has not been sufficient to arrive at a convincing conclusion.Moreover, the experimental results also show that the average degree of the MDSs of some networks tends to be greater than that of the overall network, even when the MDSs are obtained using previous research method.Further analysis shows that whether the driver nodes tend to be high-degree nodes or not is closely related to the edge direction of the network.

View Article: PubMed Central - PubMed

Affiliation: College of Information Science and Engineering, Northeastern University, Shenyang, China.

ABSTRACT
Minimum driver node sets (MDSs) play an important role in studying the structural controllability of complex networks. Recent research has shown that MDSs tend to avoid high-degree nodes. However, this observation is based on the analysis of a small number of MDSs, because enumerating all of the MDSs of a network is a #P problem. Therefore, past research has not been sufficient to arrive at a convincing conclusion. In this paper, first, we propose a preferential matching algorithm to find MDSs that have a specific degree property. Then, we show that the MDSs obtained by preferential matching can be composed of high- and medium-degree nodes. Moreover, the experimental results also show that the average degree of the MDSs of some networks tends to be greater than that of the overall network, even when the MDSs are obtained using previous research method. Further analysis shows that whether the driver nodes tend to be high-degree nodes or not is closely related to the edge direction of the network.

Show MeSH
Degree distribution of driver nodes in real and model networks.The MDS with the highest average degree <kDmax> was computed by using the preferential matching method. Each point corresponds to the set of nodes with the specific degree k, the black point means that no node with the degree k appeared in the result MDS and the red point means that some nodes with the degree k appeared in the result MDS. The inset graph shows the degree distribution of all driver nodes of the MDS with <kDmax>.
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4222963&req=5

pone-0112039-g003: Degree distribution of driver nodes in real and model networks.The MDS with the highest average degree <kDmax> was computed by using the preferential matching method. Each point corresponds to the set of nodes with the specific degree k, the black point means that no node with the degree k appeared in the result MDS and the red point means that some nodes with the degree k appeared in the result MDS. The inset graph shows the degree distribution of all driver nodes of the MDS with <kDmax>.

Mentions: To further verify the above observation, we analyzed the degree distribution of driver nodes of the MDSs with high <kD>. We computed the MDS with the highest average degree <kDmax> by using the preferential matching method. Figure 3 shows the results of some real and model networks. In Figure 3, each point corresponds to the set of nodes with the specific degree k. The black point means that no node with the degree k appears in the result MDS, and the red point means that some nodes with the degree k appear in the result MDS. The inset graph shows the degree distribution of all driver nodes of the MDS with <kDmax>. Therefore, if all red points have high degree, the MDS tends to be composed of high-degree nodes. It can be seen from Figure 3 that there do exist the MDS mainly composed of high- or medium- degree nodes in some networks. Taking the world-trade38 network as an example, 66.2% of its nodes have k≤20, but none of these low-degree nodes appeared in the result MDS; meanwhile, 88.9% of the rest high-degree nodes with k>20 appeared in the MDS. Similar results can be observed in the BA and ER networks. However, not all networks had the MDS mainly composed of high-degree nodes. The MDS with <kDmax> of some networks was composed of the nodes with degree ranging from the lowest degree to the highest, such as the seagrass[26], florida[27] and c. elegans[29] networks, while the MDS with <kDmax> of other networks was mainly composed of the low-degree nodes, such as the P2P-1 [33] network.


Structural controllability of complex networks based on preferential matching.

Zhang X, Lv T, Yang X, Zhang B - PLoS ONE (2014)

Degree distribution of driver nodes in real and model networks.The MDS with the highest average degree <kDmax> was computed by using the preferential matching method. Each point corresponds to the set of nodes with the specific degree k, the black point means that no node with the degree k appeared in the result MDS and the red point means that some nodes with the degree k appeared in the result MDS. The inset graph shows the degree distribution of all driver nodes of the MDS with <kDmax>.
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4222963&req=5

pone-0112039-g003: Degree distribution of driver nodes in real and model networks.The MDS with the highest average degree <kDmax> was computed by using the preferential matching method. Each point corresponds to the set of nodes with the specific degree k, the black point means that no node with the degree k appeared in the result MDS and the red point means that some nodes with the degree k appeared in the result MDS. The inset graph shows the degree distribution of all driver nodes of the MDS with <kDmax>.
Mentions: To further verify the above observation, we analyzed the degree distribution of driver nodes of the MDSs with high <kD>. We computed the MDS with the highest average degree <kDmax> by using the preferential matching method. Figure 3 shows the results of some real and model networks. In Figure 3, each point corresponds to the set of nodes with the specific degree k. The black point means that no node with the degree k appears in the result MDS, and the red point means that some nodes with the degree k appear in the result MDS. The inset graph shows the degree distribution of all driver nodes of the MDS with <kDmax>. Therefore, if all red points have high degree, the MDS tends to be composed of high-degree nodes. It can be seen from Figure 3 that there do exist the MDS mainly composed of high- or medium- degree nodes in some networks. Taking the world-trade38 network as an example, 66.2% of its nodes have k≤20, but none of these low-degree nodes appeared in the result MDS; meanwhile, 88.9% of the rest high-degree nodes with k>20 appeared in the MDS. Similar results can be observed in the BA and ER networks. However, not all networks had the MDS mainly composed of high-degree nodes. The MDS with <kDmax> of some networks was composed of the nodes with degree ranging from the lowest degree to the highest, such as the seagrass[26], florida[27] and c. elegans[29] networks, while the MDS with <kDmax> of other networks was mainly composed of the low-degree nodes, such as the P2P-1 [33] network.

Bottom Line: Therefore, past research has not been sufficient to arrive at a convincing conclusion.Moreover, the experimental results also show that the average degree of the MDSs of some networks tends to be greater than that of the overall network, even when the MDSs are obtained using previous research method.Further analysis shows that whether the driver nodes tend to be high-degree nodes or not is closely related to the edge direction of the network.

View Article: PubMed Central - PubMed

Affiliation: College of Information Science and Engineering, Northeastern University, Shenyang, China.

ABSTRACT
Minimum driver node sets (MDSs) play an important role in studying the structural controllability of complex networks. Recent research has shown that MDSs tend to avoid high-degree nodes. However, this observation is based on the analysis of a small number of MDSs, because enumerating all of the MDSs of a network is a #P problem. Therefore, past research has not been sufficient to arrive at a convincing conclusion. In this paper, first, we propose a preferential matching algorithm to find MDSs that have a specific degree property. Then, we show that the MDSs obtained by preferential matching can be composed of high- and medium-degree nodes. Moreover, the experimental results also show that the average degree of the MDSs of some networks tends to be greater than that of the overall network, even when the MDSs are obtained using previous research method. Further analysis shows that whether the driver nodes tend to be high-degree nodes or not is closely related to the edge direction of the network.

Show MeSH