隨機圖中k-獨立集的相變性質

盧友軍 許道云

(貴州大學計算機科學與技術學院 貴陽 550025)

隨機圖中k-獨立集的相變性質

盧友軍 許道云

(貴州大學計算機科學與技術學院 貴陽 550025)

(yjlu111@126.com)

相變性質；隨機圖；k-獨立集；臨界概率；臨界邊數

給定一個簡單無向圖G=(V,E)，V表示圖G的頂點集合，E表示圖G的邊集合.一個頂點子集T?V稱為圖G的獨立集[1](independent set, IS)，是指對任意的頂點u,v∈T都有(u,v)?E.若頂點子集T的元素個數為k，則我們稱該頂點子集T為k-獨立集.若獨立集T不是其他任何一個獨立集S的真子集，則我們稱該獨立集T為圖G的極大獨立集.若獨立集T是頂點個數最大的獨立集，則我們稱該獨立集T為圖G的最大獨立集[2](maximum independent set, MIS).MIS問題是指在一個給定的簡單無向圖G中找一個頂點個數最大的獨立集，該問題是組合優化領域中的著名NP-完全問題[3].MIS問題在編碼理論[4]、計算機網絡以及計算機視覺等領域都有重要應用.

本文的主要工作是研究隨機圖G(n,p)和隨機圖G(n,m)中k-獨立集出現相變的臨界概率和臨界邊數，其目的是讓我們對隨機圖G(n,p)和隨機圖G(n,m)中k-獨立集的結構有更加深入的理解.

1 基礎知識及記號

本節首先給出經典ER隨機圖模型的定義[16]，然后給出基本概念以及與ER隨機圖有關的一個重要結果.

一個圖性質Q是指當G∈Q，H∈G(n,p)且G?H(G同構于H)時有H∈Q，其中，G∈Q表示圖G中有圖性質Q.若該圖性質滿足條件：G∈Q并且G?H時蘊含H∈Q，則稱該圖性質Q是單調遞增的.

如果F?G?H且F,H都滿足性質Q，則G也滿足性質Q，稱圖G的性質Q是凸的.

設Q是一個圖性質，如果:

成立，則稱函數h(n)是性質Q的一個臨界函數.如果對于任意的ε>0，有:

成立，則稱函數h(n)是性質Q的一個嚴格臨界函數.

2 k-獨立集存在的相變分析

證明. 假設Γ是頂點個數為k的所有頂點子集構成的集合，其元素包含在V(G)中，其中，V(G)表示圖G∈G(n,p)的頂點集，其頂點總數為n.為描述方便，用α,β,γ,…表示Γ中的元素.記Jα是關于隨機圖G(n,p)的示性隨機變量.

如果頂點集α是圖G∈G(n,p)的一個k-獨立集，則Jα=1；否則，Jα=0.

證畢.

(1)

(2)

(3)

當c>1時，有

(4)

(5)

其中:

(6)

(7)

(8)

證畢.

其中，[x]為取整函數.

3 獨立集算法

給定一個圖G=(V,E)，V表示圖G的頂點集合，E表示圖G的邊集合.若頂點集合V的頂點子集T中任意2個節點u，v之間都沒有邊，則稱該頂點子集T為圖G的獨立集.若頂點子集T的元素個數為k，則稱該頂點子集T為k-獨立集.下面給出獨立集的求解算法1[19]：

算法1. 獨立集求解算法.

輸入：簡單無向圖G=(V,E)，整數k≥2，其中，|V|=n;

輸出：獨立集|S|≥k，其中|S|表示獨立集S中的元素個數.

Step1. 對圖G中的每個頂點用數字i=1,2,…,n標記，即V={1,2,…,n}.

Step2. 當i≤n時，初始化獨立集Si={i}，同時執行I=V-i∪N(i)；如果I=?，此時|Si|=1，那么執行i=i+1，然后轉回Step2；否則，轉到Step3.

Step3. 當|Si|

Step5. 若|Si|

Step6. 若|Si|≥k，則輸出Si程序終止；否則，轉到Step3.

4 數值實驗分析

本節的主要工作是進行數值仿真實驗分析，該實驗主要基于3個算法：1)隨機圖G(n,p)實例產生算法[6,20]；2)隨機圖G(n,m)實例產生算法[6,20]；3)獨立集算法[19].數值實驗的具體操作方法是首先利用隨機圖G(n,p)(或G(n,m))算法產生一個隨機圖實例，然后調用獨立集算法判斷圖G∈G(n,p)(或G∈G(n,m))中是否存在k-獨立集.判斷方法主要是看獨立集算法在圖G中是否能找到一個節點數不小于k的獨立集，若獨立集算法找到的獨立集的節點數不小于k，則確定在G∈G(n,p)(或G∈G(n,m))中存在一個k-獨立集，否則，我們確定在G∈G(n,p)(或G∈G(n,m))中不存在k-獨立集.

從定理1可知，隨機圖G(n,p)中k-獨立集性質出現相變的臨界概率pc與節點總數n和獨立集節點數k有關.所以，在模擬隨機圖G(n,p)中k-獨立集性質的相變現象時，分別取節點總數n值為100，200，300，400，500，獨立集節點數k值為5，10，15，20，25，如表1所示:

Table 1 Comparison Between the Theoretical Threshold and the Numerical Simulations for the Existence of k-Independent Set in Random Graph G(n,p)

表1 隨機圖G(n,p)中存在k-獨立集的理論臨界和仿真臨界的對比

kn=100n=200n=300n=400n=500TheorySimulationTheorySimulationTheorySimulationTheorySimulationTheorySimulation50．900．800．930．860．940．880．950．900．960．91100．640．680．690．790．720．830．740．840．750．85150．480．650．530．770．560．800．580．830．590．84200．380．630．430．760．450．790．470．820．480．84250．320．590．360．740．380．780．390．810．400．83

Fig. 1 Phase transition of 10-IS in random graph G(n,p)圖1 隨機圖G(n,p)中10-獨立集的相變

圖1給出了當獨立集節點數k固定時隨機圖G(n,p)中存在k-獨立集的臨界概率pc隨節點總數n的變化情況，這里取獨立集節點數k=10，節點總數n分別取值為100，200，300，400，500.圖1中的每個數據點是對每個給定的概率p和節點總數n利用隨機圖G(n,p)生成算法生成的100個圖G∈G(n,p)實例中存在10-獨立集的統計概率.

從圖1可以看出，當獨立集節點數k=10固定時，隨機圖G(n,p)中存在10-獨立集的臨界概率pc隨節點總數n的增加而增加，而且臨界概率pc向右移動.

圖2給出了當節點總數n固定時隨機圖G(n,p)中k-獨立集出現相變的臨界概率pc隨獨立集節點數k的變化情況，這里取節點總數n=400，獨立集節點數k分別取值為5，10，15，20，25.圖2中的每個數據點是對每個給定的概率p和節點總數n利用隨機圖G(n,p)生成算法生成的100個圖G∈G(n,p)實例中存在k-獨立集的統計概率.從圖2可以看出，當節點總數n=400固定時，隨機圖G(n,p)中存在k-獨立集的臨界概率pc隨獨立集節點數k的增加而減小，而且臨界值pc向左移動.

Fig. 2 Phase transition of k -IS in random graph G(n,p)圖2 隨機圖G(n,p)中k-獨立集的相變

Table 2 Comparison Between the Theoretical Threshold and the Numerical Simulations for the Existence of k-Independent Set in Random Gandom Graph G(n,m)

表2 隨機圖G(n,m)中存在k -獨立集的理論臨界邊數和仿真臨界邊數對比

kn=100n=200n=300n=400n=500TheorySimulationTheorySimulationTheorySimulationTheorySimulationTheorySimulation5445540001849317114422613906375810710221191711135681031713550137691572132223368185872567830933981073281523863350105651532324994363694589466234734081060802019023250850615124202463592037328654365989610483225157830507103149251696735022313646463850426103584

圖3給出了當獨立集的節點數k固定時隨機圖G∈G(n,m)中存在k-獨立集的臨界邊數mc隨節點總數n的變化情況，這里分別取獨立集節點數k=10，節點總數n分別取值為100，200，300，400，500.圖3中的每個數據點是對每個給定的邊數m和節點總數n利用隨機圖G(n,m)生成算法生成的100個圖G∈G(n,m)實例中存在k-獨立集的統計概率.從圖3可以看出，當固定獨立集節點數k=10時，隨機圖G(n,m)中存在k-獨立集的臨界邊數mc隨節點總數n的增加而增加，臨界邊數mc向右移.

Fig. 3 Phase transition of 10-IS in random graph G(n,m)圖3 隨機圖G(n,m)中10-獨立集的相變

圖4給出了當節點總數n固定時隨機圖G(n,m)中k-獨立集出現相變的臨界邊數mc隨獨立集的節點數k的變化情況，這里分別取節點總數n=200，獨立集節點數k分別取值為5，10，15，20，25.圖4中的每個數據點是對每個給定的邊數m和節點總數n利用隨機圖G(n,m)生成算法生成的100個圖G∈G(n,m)實例中存在k-獨立集的統計概率.從圖4可以看出，當固定頂點數n=200時，隨機圖G(n,m)中存在k-獨立集的臨界邊數mc隨著獨立集節點數k的增加而減小，臨界邊數mc向左移.

Fig. 4 Phase transition of k -IS in random graph G(n,m)圖4 隨機圖G(n,m)中k -獨立集的相變

5 結束語

[1]Coja-Oghlan A, Efthymiou C. On independent sets in random graphs[J]. Random Structures & Algorithms, 2014, 47(3): 136-144

[2] Zhao Chunxiao, Wang Guangxing. Aδ-degree-based clustering algorithm in MANET[J]. Journal of Computer Research and Development, 2005, 42(5): 818-822 (in Chinese)(趙春曉, 王光興. 一種δ-度約束的自組網成簇算法[J]. 計算機研究與發展, 2005, 42(5): 818-822)

[3] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. New York: W H Freeman and Company, 1979

[4] Sloane N J A. Unsolved problem in graph theory arising from the study of codes[J]. Graph Theory Notes of New York, 1989, 18(11): 11-20

[5] Erd?s P, Rényi A. On random graphs I[J]. Publicationes Mathematicae, 1959(6): 290-297

[6] Wang Xiaofan, Li Xiang, Chen Guanrong. Network Science: An Introduction[M]. Beijing: Higher Education Press, 2012: 200-201 (in Chinese)(汪小帆, 李翔, 陳關榮. 網絡科學導論[M]. 北京: 高等教育出版社, 2012: 200-201)

[7] Hopcroft J, Kannan R. Computer Science Theory for the Information Age[M]. Shanghai: Shanghai Jiao Tong University Press, 2013: 39-72

[8] Zdeborová L, Krzakaa F. Phase transitions in the coloring of random graphs[J/OL]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2007, 76(3): Article Number 031131. [2016-09-01]. https://doi.org/10.1103/PhysRevE.76.031131

[9] Xu Ke, Li Wei. Exact phase transitions in random constraint satisfaction problems[J]. Journal of Artificial Intelligence Research, 2000, 12(1): 93-103

[10] Xu Ke, Li Wei. Many hard examples in exact phase transitions[J]. Theoretical Computer Science, 2006, 355(3): 291-302

[11] Mertens S, Zard M, Zecchina R. Threshold values of random K-SAT from the cavity method[J]. Random Structures & Algorithms, 2006, 28(3): 340-373

[12] Nekovee M, Moreno Y, Bianconi G, et al. Theory of rumour spreading in complex social networks[J]. Physica A Statistical Mechanics & Its Applications, 2008, 374(1): 457-470

[13] Gómezgardees J, Lotero L, Taraskin S N, et al. Explosive contagion in networks[J/OL]. Scientific Reports, 2016, 6(1): Article Number 19767. [2016-09-01]. https://doi.org/10.1038/srep19767

[14] Culberson J, Gao Yong, Anton C. Phase transitions of dominating clique problem and their implications to heuristics in satisfiability search[DB]. Trier, Rheinland-Pfalz, Germany: DBLP, 2005 [2016-09-01]. http://dblp.org/db/conf/ijcai/ijcai2005.html

[15] Nehéz M, Olejár D, Demetrian M. A detailed study of the dominating cliques phase transition in random graphs[C] //Proc of the 9th Annual Int Conf on Theory and Applications of Models of Computation. Berlin: Springer, 2012: 594-603

[16] Bollobasi B. Random Graphs[M]. New York: Academic Press, 2001

[17] Seierstad T G. The phase transition in random graphs and random graph processes[D]. Berlin: Humboldt University, 2007

[18] Nehéz M, Olejár D, Demetrian M. On emergence of dominating cliques in random graphs[EB/OL]. 2008 [2016-09-01]. https://arxiv.org/abs/0805.2105

[19]Dharwadker A. The independent set algorithm[OL]. 2006 [2016-09-01]. http://www.dharwadker.org/independent_set/

[20] Nobari S, Lu X, Karras P, et al. Fast random graph generation[C] //Proc of the 14th Int Conf on Extending Database Technology. New York: ACM, 2011: 331-342

PhaseTransitionPropertiesofk-IndependentSetsinRandomGraphs

Lu Youjun and Xu Daoyun

(CollegeofComputerScienceandTechnology,GuizhouUniversity,Guiyang550025)

phase transition property; random graphs;k-independent set; threshold probability; threshold edge number

2016-09-14；

2016-12-05

國家自然科學基金項目(61262006，61462001，61540050，61762019)；貴州省重大應用基礎研究項目(JZ20142001)；貴州大學研究生創新基金項目(2016047)

This work was supported by the National Natural Science Foundation of China (61262006, 61462001, 61540050, 61762019), the Major Applied Basic Research Program of Guizhou Province (JZ20142001), and the Graduate Student Innovation Foundation of Guizhou University (2016047).

許道云(dyxu@gzu.edu.cn)

TP301

LuYoujun, born in 1985. PhD candidate. Student member of CCF. His main research interests include computational complexity and complex networks.

XuDaoyun, born in 1959. Professor and PhD supervisor at the College of Computer Science and Technology, Guizhou University. Senior member of CCF. His main research interests include computability theory and computational complexity.