在線社會網(wǎng)絡(luò)結(jié)構(gòu)、演化及運(yùn)行

在線社會網(wǎng)絡(luò)結(jié)構(gòu)、演化及運(yùn)行

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