改進HK網絡演化模型的研究

徐玉珠,張達敏,曾　成,孫雅倩

(貴州大學 大數據與信息工程學院,貴州 貴陽　550025)

?

改進HK網絡演化模型的研究

徐玉珠,張達敏,曾成,孫雅倩

(貴州大學 大數據與信息工程學院,貴州 貴陽550025)

摘要以HK網絡模型為基礎,提出了兩個度分布與聚類系數均可調的改進HK網絡模型。改進模型聯合考慮“優先連接”、“三角結構”、“內部演化”等演化機制。在新節點加入時,分別考慮加入單個節點和社團的情況,將 TF 機理移到舊節點之間進行網絡演化。仿真結果表明,兩個改進模型不僅繼承了HK模型的高聚類無標度特性,同時克服了HK模型演化過程中單一加入單個節點的方式及新舊節點之間TF機理的限制。

關鍵詞HK模型;度分布;聚類系數

Research on and Modeling of the Improved HK Network Model

XU Yuzhu,ZHANG Damin,ZENG Cheng,SUN Yaqian

(College of Big Data and Information Engineering,Guizhou University,Guiyang 550025,China)

AbstractTwo improved HK network models based on the HK network model with adjustable degree distribution and clustering coefficient are proposed.The improved models jointly consider the evolution mechanisms of preferential attachment,triangle structure,and internal evolution.The mechanism of TF moved to old nodes in the evolution of network when a new node (a single node or a community) joins in the network.Simulation results show that the two improved models not only inherit the high clustering and scale free properties but also overcome the single way of node joint and the TF mechanism limit between new and old nodes.

KeywordsHK model;degree distribution;clustering coefficient

在復雜網絡的研究歷史上,匈牙利數學家Erd?s和Rényi建立的隨機圖論奠定了復雜網絡理論研究的基礎[1]。隨后,Watts和Strogatz提出的“WS小世界網絡”揭示了復雜網絡的小世界特征[2],聚類系數高、平均路徑長度短。Barabási和Albert結合實際網絡的特性,建立了兼具增長機制和優先連接特性的“BA無標度網絡”[3-4],其節點的度服從冪律分布。然而實際網絡幾乎同時具備高聚類無標度特性。最早的高聚類系數無標度網絡模型是 Holme-Kim(HK)模型,也是最具代表性的此類模型之一。HK模型以BA模型為基礎,增加了一種TF(Triad Formation)的方法,以此改變原模型中加入的新節點均按照全局擇優PA(Preferential Attachment)原則來選擇舊節點進行加邊的方式。這種改進不僅使得網絡增長方式更靈活,也提高了聚類系數[5]。

但在HK模型的演化過程中,每個時間步加入的新節點n均產生相同的新邊數m與網絡中的已存在節點相連,且網絡中新邊的產生只存在于新、舊節點之間。……