基于模体的目标区域网络拓扑划分方法
|
摘要
随着信息社会的发展,网络安全的重要性日益凸显,准确获取网络实体的地理位置有助于更好地实施网络管理。现有经典的基于拓扑启发式聚类的网络实体定位方法,采用基于网络结构的集群划分对网络实体进行聚类,由于没有考虑网络拓扑的具体特性,导致最后的结果误差较大。为解决这一问题,提出一种基于模体的目标区域网络拓扑划分方法。该方法根据目标网络拓扑呈现局部节点高聚类性的特点,创新性地引入"模体"的概念,在目标网络拓扑中挖掘模体结构并进行分析;然后借鉴复杂网络研究领域内局部社团发现方法中初始种子扩展的思路,以模体结构为初始种子进行相应扩展,将拓扑中与模体紧密相连的节点划分为多个集合;最后分别根据地标和公开的IP地理位置数据库对划分的节点集合进行定位,将集合的位置作为集合内节点的地理位置,从而实现网络实体的批量定位。基于香港和台湾两个地区网络拓扑的实验结果表明,该方法与经典的HC-Based方法、NNC方法相比,在网络实体定位准确率上分别能提高25%和16%左右,并且可批量定位的网络实体更多。
With the development of the information society, the importance of network security has become increasingly prominent, and the accurate geographical location of network entities can help better implement network management. The existing classical network entity location method based on topology heuristic clustering adopts the clustering based on network structure to cluster network entities, does not consider the specific characteristics of the network topology, and leads to final results with big error. In order to solve this problem, we propose a target area network topology partitioning method based on the motifs. According to the high clustering characteristics of local nodes in the target network topology, we innovatively introduce the concept of "motif" and analyze the motif structure in the target network topology. Learning from the idea of the initial seed expansion in local community discovery methods for the complex network, we take the motif structure as the initial seed to expand, and divide the nodes closely connected with the motif in the topology into different sets. Finally we locate the node sets according to the landmark and the public IP geo-location database, and take the location of the set as the geographic location of the nodes within it so as to achieve the bulk positioning of network entities. Experiments based on the network topologies in Hong Kong and Taiwan show that compared with the classical HC-Based method and network node clustering method(NNC), the positioning accuracy of network entities of our method can be enhanced by about 25% and 16% respectively, and there are more network entities can be located in a batch way.
With the development of the information society, the importance of network security has become increasingly prominent, and the accurate geographical location of network entities can help better implement network management. The existing classical network entity location method based on topology heuristic clustering adopts the clustering based on network structure to cluster network entities, does not consider the specific characteristics of the network topology, and leads to final results with big error. In order to solve this problem, we propose a target area network topology partitioning method based on the motifs. According to the high clustering characteristics of local nodes in the target network topology, we innovatively introduce the concept of "motif" and analyze the motif structure in the target network topology. Learning from the idea of the initial seed expansion in local community discovery methods for the complex network, we take the motif structure as the initial seed to expand, and divide the nodes closely connected with the motif in the topology into different sets. Finally we locate the node sets according to the landmark and the public IP geo-location database, and take the location of the set as the geographic location of the nodes within it so as to achieve the bulk positioning of network entities. Experiments based on the network topologies in Hong Kong and Taiwan show that compared with the classical HC-Based method and network node clustering method(NNC), the positioning accuracy of network entities of our method can be enhanced by about 25% and 16% respectively, and there are more network entities can be located in a batch way.
引文
[1] Floyd S,Paxson V.Difficulties in simulating the Internet[J].IEEE/ACM Transactions on Networking,2002,9(4):392-403.
[2] Knight S,Nguyen H X,Falkner N,et al.The internet topology zoo[J].IEEE Journal on Selected Areas in Communications,2011,29(9):1765-1775.
[3] Milo R,Shenorr S,Itzkovitz S,et al.Network motifs:Simple building blocks of complex networks[J].Science,2002,298(5594):824-827.
[4] Clauset A. Finding local community structure in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2005,72(2):026132.
[5] Palla G,Derenyi I,Farkas I J,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[6] Lancichinetti A,Fortunato S,Kertész J.Detecting the overlapping and hierarchical community structure of complex networks[J].New Journal of Physics,2008,11(3):19-44.
[7] Lee C,Reid F,Mcdaid A,et al.Detecting highly overlapping community structure by greedy clique expansion[C]//Proc of 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Minging(ASONAM2014),2014:196-199.
[8] Chen Qiong,Wu Ting-ting, Fang Ming.Detecting local community structures in complex networks based on local degree central nodes[J].Physica A:Statistical Mechanics & its Applications,2013,392(3):529-537.
[9] Zhao Wen-tao,Zhao Hao-hao,Meng Ling-jun.Local community discovery algorithm based on node cohesion coefficient[J].Journal of Computer Applications and Software,2016,33(12):270-274.(in Chinese)
[10] Mangan S,Alon U.Structure and function of the feed-forward loop network motif[J].Proceedings of the National Academy of Sciences of the United States of America,2003,100(21):11980-11985.
[11] Milo R,Itzkovitz S,Kashtan N,et al.Superfamilies of designed and evolved networks[J].Science, 2004,303(5663):1538-1542.
[12] Krumov L A. Local structures determine performance within complex network[D].Saarbrücken:Suedwestdeutscher Verlag fuer Hochschulschriften, 2010.
[13] Kashtan N,Itzkovitz S,Milo R,et al.Efficient sampling algorithm for estimating sub-graph concentrations and detecting network motifs[J].Bioinformatics,2004,20 (11):1746-1758.
[14] Wernicke S.A faster algorithm for detecting network motifs[C]//Proc of International Workshop on Algorithms in Bioinformatics,2005:165-177.
[15] Wernicke S.Efficient detection of network motifs[J].IEEE/ACM Transactions on Computational Biology & Bioinformatics,2006,3(4):347-359.
[16] Omidi S,Schreiber F,Masoudi-Nejad A.MODA:An efficient algorithm for network motif discovery in biological networks[J].Genes & Genetic Systems,2009,84(5):385-395.
[17] Berg J,L?ssig M.Local graph alignment and motif search in biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2004,101(41):14689-14694.
[18] Mukherjee K,Hasan M M,Boucher C,et al.Counting motifs in dynamic networks[J].Bmc Systems Biology,2018,12(1):6.
[19] Luo J,Ding L,Liang C,et al.An efficient network motif discovery approach for co-regulatory networks[J].IEEE Access,2018,6:14151-14158.
[20] Shue C A,Gupta M.An Internet without the Internet protocol[J].Computer Networks,2010,54(18):3232-3245.
[21] Backhaus M,Sch?fer G.Towards optimally resilient topologies against optimal attacks[C]//Proc 2017 IFIP/IEEE Symposium on Integrated Network and Service Management, 2017:1065-1070.
[22] Tian Ye,Dey R,Liu Y,et al.Topology mapping and geolocating for China’s Internet [J].IEEE Transactions on Parallel and Distributed Systems,2013,24(9):1908-1917.
[23] Liu S,Liu F,Zhao F,et al.IP city-level geolocation based on the PoP-level network topology analysis[C]//Proc of International Conference on Information Communication and Management,2016:109-114.
[24] Li M,Luo X,Shi W,et al.City-level IP geolocation based on network topology community detection[C]//Proc of International Conference on Information Networking,2017:578-583.
[25] Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008,2008(10):1008-1016.
[26] Zhang Guo-qing.Internet topology knowledge discovery and its application[J].Journal of Communications,2010,31(10):18-25.(in Chinese)
[27] Qian Xue-sen. On system engineering [M].Shanghai:Shanghai Jiaotong University Press,2007.(in Chinese)
[28] Wernicke S,Rasche F.FANMOD:A tool for fast network motif detection[J].Bioinformatics,2006,22(9):1152-1153.
[29] Fisher R A.On a distribution yielding the error function of several wellknown statistics[C]//Proc of the International Congress of Mathematics,1924:1.
[9] 赵文涛,赵好好,孟令军.基于节点内聚系数的局部社团发现算法[J].计算机应用与软件,2016,33(12):270-274.
[26] 张国清.互联网拓扑结构知识发现及其应用[J].通信学报,2010,31(10):18-25.
[27] 钱学森.论系统工程[M].上海:上海交通大学出版社,2007.
[2] Knight S,Nguyen H X,Falkner N,et al.The internet topology zoo[J].IEEE Journal on Selected Areas in Communications,2011,29(9):1765-1775.
[3] Milo R,Shenorr S,Itzkovitz S,et al.Network motifs:Simple building blocks of complex networks[J].Science,2002,298(5594):824-827.
[4] Clauset A. Finding local community structure in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2005,72(2):026132.
[5] Palla G,Derenyi I,Farkas I J,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[6] Lancichinetti A,Fortunato S,Kertész J.Detecting the overlapping and hierarchical community structure of complex networks[J].New Journal of Physics,2008,11(3):19-44.
[7] Lee C,Reid F,Mcdaid A,et al.Detecting highly overlapping community structure by greedy clique expansion[C]//Proc of 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Minging(ASONAM2014),2014:196-199.
[8] Chen Qiong,Wu Ting-ting, Fang Ming.Detecting local community structures in complex networks based on local degree central nodes[J].Physica A:Statistical Mechanics & its Applications,2013,392(3):529-537.
[9] Zhao Wen-tao,Zhao Hao-hao,Meng Ling-jun.Local community discovery algorithm based on node cohesion coefficient[J].Journal of Computer Applications and Software,2016,33(12):270-274.(in Chinese)
[10] Mangan S,Alon U.Structure and function of the feed-forward loop network motif[J].Proceedings of the National Academy of Sciences of the United States of America,2003,100(21):11980-11985.
[11] Milo R,Itzkovitz S,Kashtan N,et al.Superfamilies of designed and evolved networks[J].Science, 2004,303(5663):1538-1542.
[12] Krumov L A. Local structures determine performance within complex network[D].Saarbrücken:Suedwestdeutscher Verlag fuer Hochschulschriften, 2010.
[13] Kashtan N,Itzkovitz S,Milo R,et al.Efficient sampling algorithm for estimating sub-graph concentrations and detecting network motifs[J].Bioinformatics,2004,20 (11):1746-1758.
[14] Wernicke S.A faster algorithm for detecting network motifs[C]//Proc of International Workshop on Algorithms in Bioinformatics,2005:165-177.
[15] Wernicke S.Efficient detection of network motifs[J].IEEE/ACM Transactions on Computational Biology & Bioinformatics,2006,3(4):347-359.
[16] Omidi S,Schreiber F,Masoudi-Nejad A.MODA:An efficient algorithm for network motif discovery in biological networks[J].Genes & Genetic Systems,2009,84(5):385-395.
[17] Berg J,L?ssig M.Local graph alignment and motif search in biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2004,101(41):14689-14694.
[18] Mukherjee K,Hasan M M,Boucher C,et al.Counting motifs in dynamic networks[J].Bmc Systems Biology,2018,12(1):6.
[19] Luo J,Ding L,Liang C,et al.An efficient network motif discovery approach for co-regulatory networks[J].IEEE Access,2018,6:14151-14158.
[20] Shue C A,Gupta M.An Internet without the Internet protocol[J].Computer Networks,2010,54(18):3232-3245.
[21] Backhaus M,Sch?fer G.Towards optimally resilient topologies against optimal attacks[C]//Proc 2017 IFIP/IEEE Symposium on Integrated Network and Service Management, 2017:1065-1070.
[22] Tian Ye,Dey R,Liu Y,et al.Topology mapping and geolocating for China’s Internet [J].IEEE Transactions on Parallel and Distributed Systems,2013,24(9):1908-1917.
[23] Liu S,Liu F,Zhao F,et al.IP city-level geolocation based on the PoP-level network topology analysis[C]//Proc of International Conference on Information Communication and Management,2016:109-114.
[24] Li M,Luo X,Shi W,et al.City-level IP geolocation based on network topology community detection[C]//Proc of International Conference on Information Networking,2017:578-583.
[25] Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008,2008(10):1008-1016.
[26] Zhang Guo-qing.Internet topology knowledge discovery and its application[J].Journal of Communications,2010,31(10):18-25.(in Chinese)
[27] Qian Xue-sen. On system engineering [M].Shanghai:Shanghai Jiaotong University Press,2007.(in Chinese)
[28] Wernicke S,Rasche F.FANMOD:A tool for fast network motif detection[J].Bioinformatics,2006,22(9):1152-1153.
[29] Fisher R A.On a distribution yielding the error function of several wellknown statistics[C]//Proc of the International Congress of Mathematics,1924:1.
[9] 赵文涛,赵好好,孟令军.基于节点内聚系数的局部社团发现算法[J].计算机应用与软件,2016,33(12):270-274.
[26] 张国清.互联网拓扑结构知识发现及其应用[J].通信学报,2010,31(10):18-25.
[27] 钱学森.论系统工程[M].上海:上海交通大学出版社,2007.