在線社會網絡結構、演化及運行

在線社會網絡結構、演化及運行

1社會網絡的度異配性20世紀的繁榮和發(fā)展，加深了對世界極其復雜的社會系統(tǒng)的理解。近年來,隨著信息技術的發(fā)展以及Web2.0技術的廣泛應用,互聯(lián)網上涌現(xiàn)出很多在線的社會網絡。這些社會網絡的規(guī)模異常龐大且時刻處于動態(tài)變化之中,因而需要將傳統(tǒng)的社會網絡分析和現(xiàn)代的復雜網絡研究結合起來才有可能理解人與人之間相互作用的模式和動力學過程。在線社會網絡的結構及運行其上的動力學過程,近年來已引起了不同學科研究人員的關注。研究Web社區(qū)中個體之間的關系及人的在線行為是近年來信息科學領域非常關心的問題?；ヂ?lián)網上人與人之間的關系和相互作用可以用在線社會網絡來描述,用戶為節(jié)點,而用戶之間的好友關系則為連邊。我們重點研究了在線社會網絡的結構、演化及運行其上的輿論動力學過程。對中國國內一個大型的在線職業(yè)人士社交網——若鄰網(Wealink)進行了研究。發(fā)現(xiàn)該網絡具有小世界特性、高聚類系數(shù)、層次化結構和社團性等與一般的現(xiàn)實社會網絡相似的共性,同時也表現(xiàn)出了自己的特性:度分布具有無標度特性,連通子圖規(guī)模分布、度分布和社團規(guī)模分布呈現(xiàn)出鋸齒狀以及度異配性。網絡的功能對結構有顯著的影響,通過模型闡明了該網絡的度分布形成的機制,并探討了在線社會網絡度異配性的起源。我們還研究了Wealink的網絡結構演化特性。研究發(fā)現(xiàn)其規(guī)模增長表現(xiàn)出非平凡的S型,進而為Web社區(qū)中的Bass擴散模型提供了一個例證。與傳統(tǒng)的網絡增長模型所預測的不同,真實網絡的密度、聚類系數(shù)、異質系數(shù)和模塊度隨著時間的增長表現(xiàn)出非單調特性,且平均路徑長度和直徑出現(xiàn)收縮現(xiàn)象。特別地,首次揭示了在線社會網絡從同配網絡到異配網絡的轉變,并構建了一網絡模型以闡明該躍變過程。針對Wealink中的用戶行為的研究發(fā)現(xiàn),發(fā)出的連接請求被快速地響應,互惠時間分布為指數(shù)分布。此外,邀請者/接收者的度值幾乎與互惠時間無關。用戶行為之間的時間間隔分布,即用戶發(fā)出邀請之間、接受邀請之間或任意兩個事件之間的時間間隔分布滿足指數(shù)相同的冪律。我們研究了優(yōu)先連接現(xiàn)象,發(fā)現(xiàn)對于優(yōu)先接受、優(yōu)先創(chuàng)建和優(yōu)先依附3種情況,線性優(yōu)先性均成立。我們研究了在線社會系統(tǒng)中個體的活動性和流行度。實證研究發(fā)現(xiàn)個體流行度或活動性的分布服從冪律或延拓指數(shù)分布,且活動性對人類動力學有顯著影響,活躍度越高,用戶行為的時間間隔分布越集中。我們構建了一概率模型闡述不同的活動性和流行度分布產生的機制,發(fā)現(xiàn)當優(yōu)先性指數(shù)β=1即線性優(yōu)先時為冪律分布,當0<β<1即亞線性優(yōu)先時為延拓指數(shù)分布,而當β=0即不存在優(yōu)先性時則退化為指數(shù)分布。研究了社會網絡中基于社會影響的離散狀態(tài)輿論動力學。初始時每個個體的狀態(tài)可取離散值i=1,2,K,I。研究發(fā)現(xiàn),對于任意的I≥2和自信參數(shù),即個體維持當前狀態(tài)的概率0≤u≤1,當u與個體度值無關時,狀態(tài)為i的個體的加權比例〈qi〉為鞅,即狀態(tài)為i的個體的總度值占網絡總度值的比例〈qi〉的均值為一常數(shù),狀態(tài)為i的個體的比例qi隨著時間的增長將逐漸收斂至〈qi〉,且隨著網絡度同配系數(shù)的增加,收斂趨勢逐漸減慢。當u與個體度值相關時,〈qi〉不再是鞅,但qi仍收斂至〈qi〉。上述兩種情況中,對于有限網絡,所有個體的狀態(tài)將最終達到一致。進一步研究了網絡中存在狀態(tài)不隨時間變化的堅定型個體的情況,研究發(fā)現(xiàn),當u與個體度值無關時,〈qi〉和qi均收斂至僅與初始時堅定型個體的分布有關的固定比例,最終的場景將是堅定型個體所處于的幾種狀態(tài)共存的平衡態(tài)。我們在無標度網絡上的數(shù)值模擬驗證了解析結果。該模型強調了度值大的個體對最終的一致態(tài)或共存態(tài)的影響,體現(xiàn)了社會網絡中輿論擴散的一些現(xiàn)實特征。2蜂預防選取及控制算法牽制控制的基本思想是:通過有選擇地對網絡中的少部分節(jié)點施加控制而使整個網絡具有期望的行為。因此,牽制控制涉及到的第1個基本問題就是可行性問題。這方面的研究目前主要集中在對部分節(jié)點施加線性反饋而使整個動態(tài)網絡穩(wěn)定在期望的同步狀態(tài)。在理論方面已經清楚的是,只要網絡的耦合強度和反饋控制增益合適,那么只需控制部分節(jié)點就能夠實現(xiàn)控制目標。牽制控制的第2個基本問題是有效性問題,即如何選取受控節(jié)點才能使達到控制目標所花的代價盡可能小。這里的代價包括所需直接控制的節(jié)點數(shù)量、網絡耦合強度和反饋控制增益幅值等。已有的研究表明,利用網絡的拓撲特性,有選擇地對網絡中少量重要的關鍵節(jié)點直接施加控制要比隨機選擇部分節(jié)點加以控制具有明顯優(yōu)勢。我們近期的研究主要集中于把牽制控制的思想用于蜂擁控制。從復雜網絡的觀點看,蜂擁行為可以看作是拓撲結構隨時間變化的動態(tài)網絡所產生的協(xié)調一致的行為,而目前關于復雜動態(tài)網絡牽制控制的研究則主要針對的是具有固定拓撲結構的網絡。目前在蜂擁控制研究中采用最多的是1986年Reynolds提出的一個用計算機來模擬蜂擁群體行為的經典的Boids模型。這個模型中的自主體(Agent)滿足3條基本規(guī)則:1)分離(Separation):與鄰域內的自主體避免相撞;2)聚合(Cohesion):與鄰域內的自主體保持緊湊;3)速度匹配(Alignment):與鄰域內的自主體速度保持一致。為了能夠保持分離,一個自主體首先需要獲得鄰域內其它自主體的位置信息。對于一個自主體來說,每一個在其鄰域范圍內的自主體與它之間有一個排斥力,這個排斥力是與它們之間的距離成反比的。每一個自主體所受到的排斥力是它鄰域范圍內其它自主體對它的排斥力的累加。為了能夠產生聚合的群體行為,一個自主體需要計算出鄰域內其它自主體位置的平均值,由此產生一個作用于該鄰域內所有自主體的吸引力,這樣使自主體向平均位置方向運動。為了能夠實現(xiàn)速度匹配,每個自主體需要獲得鄰域內其它自主體速度信息,計算出鄰域內自主體的平均速度。通過速度匹配,可以使自主體速度大小和方向與這個鄰域內所有自主體速度的平均值保持一致。2006年,Olfati-Saber提出了3個蜂擁控制算法。其中,第1個控制算法體現(xiàn)了Reynolds的3條規(guī)則,第2個控制算法具有避免與障礙物相撞的功能。第3個控制算法通過對每個自主體添加引導反饋來實現(xiàn)跟蹤目標的功能。但是,在第2個控制算法中假設每個自主體都知道虛擬領導者的信息,這種假設的好處是保證每個自主體都能夠聚合和達到期望的速度。然而,這個假設和自然中的一些實例是不相符合的,而且它在工程實際中有時也是很難實現(xiàn)的。在自然界,群體中往往只有很少的個體具有引導信息,比如食物所在的位置或者遷移的路線等等。例如:研究發(fā)現(xiàn)魚群中只有少量魚具有遷移的路線信息,但是它們能夠引導整個魚群游向期望的地點;蜂群中只有大概5%的蜜蜂知道新巢的信息,并能引導整個蜂群飛向新巢。最近,Couzin等人針對這種現(xiàn)象建立了一個離散模型,并通過仿真得到群集中只需要很少一部分個體知道引導的信息,就可以使絕大多數(shù)個體具有期望的群集行為。針對上述現(xiàn)象并受到復雜網絡牽制控制研究的啟發(fā),我們假設群體中只有一部分自主體具有虛擬領導者的信息。我們將所有的不具有引導信息的自主體分為兩大類。在無限個連續(xù)、非空和一致有界的時間間隔中,如果某個不具有引導信息的自主體始終存在一條聯(lián)合路徑連接它和某個具有引導信息的自主體,就稱該自主體為第Ⅰ類不具有引導信息的自主體;否則,就稱它為第Ⅱ類不具有引導信息的自主體。我們假設如果存在一個足夠大的時間T,當t≥T時,第Ⅱ類不具有引導信息的自主體和具有引導信息的自主體之間不存在任何聯(lián)合路徑。這個假設暗示了如果一個不具有引導信息的自主體與具有引導信息的自主體有足夠長的時間沒有直接或間接的連接,我們就認為它們之間永遠不會直接或間接相連。在這個假設條件下,當t≥T時,所有具有引導信息和第Ⅰ類不具有引導信息的自主體,都不會直接和間接受到第Ⅱ類不具有引導信息的自主體的影響。我們從理論上證明了,所有具有引導信息和第Ⅰ類不具有引導信息的自主體的速度將會漸近收斂到期望的速度。此外,我們在蜂擁控制方面也做了進一步研究,具體包括:1蜂預防控制算法針對以往所有具有虛擬領導者的蜂擁控制算法都是針對單個虛擬領導者的情形,我們首次提出了具有多個虛擬領導者的蜂擁控制算法,我們理論上證明了該算法可以使所有智能體準確跟蹤各自需跟蹤的虛擬領導者,并且證明了所有智能體的位置和速度的平均值指數(shù)收斂到所有虛擬領導者位置和速度的加權平均值。2保持網絡連通性我們提出了一個具有保持網絡連通性的蜂擁控制算法,該算法在完成所需的蜂擁控制目標的同時具有保持網絡連通性的功能,即該算法只需要初始網絡為連通就可以完成所需的蜂擁控制目標。另外,我們還研究了帶有一個虛擬領導者并且保持網絡連通性的蜂擁控制算法。在初始網絡為連通的情況下,該算法可以使所有智能體準確跟蹤到虛擬領導者,并且智能