超網絡中心性度量的υ-Position值方法

單而芳， 蔡 蕾,2， 曾 晗， 彭超婧

(1.上海大學 管理學院,上海 200444; 2.上海市第一人民醫院,上海 200080)

0 引言

在各種政治、經濟、社會等網絡中,我們常常需要識別出其中相對重要的成員，也就是網絡中的關鍵節點。例如作為網絡防護方來說,識別出網絡中的關鍵節點后可以對一些關鍵節點進行備份,或采取其他手段對其進行保護,這樣就能大幅度的提高整個網絡的魯棒性和抗毀性。再例如目前生物學領域的大量研究證實蛋白質分子的功能大小與它在復雜生物網絡拓撲結構中的重要性有著緊密聯系。因此識別出生物網絡中關鍵的蛋白質分子,對于疾病診斷、病毒研究等生物信息領域能起到關鍵作用。此外,在政治網絡如國際組織中,若能識別出對組織最重要的成員并投入相對多的關注和資源,對于該組織的穩定性和發展都將大有裨益。因此,如何度量網絡節點的重要程度,發掘出關鍵節點具有重要的理論與應用價值。

目前，已有文獻中提出的關鍵節點的識別方法主要有兩類: 一類是經典的中心性測度方法，主要基于節點在網絡結構中的位置。這需要充分挖掘網絡結構的信息,從中尋找有用信息來反映節點在結構中的顯著性。例如在某一星狀通訊網絡中,中心節點與其他每個節點都直接相連,所以它擁有的連接度是最大的, 因此可以認為它是該網絡中的中心節點。根據這一思想而提出的中心性測度方法主要有:特征向量測度、度值測度、緊密測度、中介測度等方法[1,2]。這些方法側重網絡的結構，其共同的不足是較少能應用于網絡中對政治和經濟現象的解釋。另一類中心性的測度方法是利用合作博弈理論的收益分配規則。主要有兩種: Banzhaf值法[3]和Shapley值法[4]。這些方法通過分析某一點的邊際貢獻或者該點失效后的后果來衡量其重要性。與側重網絡結構的中心性測度方法不同的是合作博弈理論能夠考慮到政治經濟因素、博弈的情境和參與者的權重。然而此類方法由于忽視合作的結構，而假設任何聯盟都是可行的，從而很可能無法準確描述網絡中各參與者的中心性。例如，在某些政治、經濟或社會背景下, 參與者的權重決策機制是不合理的, 因為在這些環境中, 聯盟的規模有時并不具有決定性的意義。 另一方面, 如果參與者之間存在互不兼容性, 那么Shapley值法是不適用的, 特別在政治網絡情境中，一旦兩個政黨之間的意識形態存在互不兼容, 那么所有潛在的由雙方參與的政府組織都將不會產生。為了避免這個缺陷，Myerson[5]在考慮合作結構的前提下，借助Shapley值提出了一種新的分配規則，也就是Myerson值。Myerson值以圖或者超圖(也就是網絡或者超網絡)作為合作結構，用圖中的節點表示參與者，圖中的邊來表示參與者之間的直接交流關系，并假設不連通的參與者之間不能形成可行聯盟。不過，Myerson值雖然考慮了網絡結構對中心性的影響，但側重突出網絡中參與者(節點)的作用，而把每條邊的地位和作用當作是一樣的。

然而，在現實中參與者之間聯系的緊密性、交流深度和合作程度有可能是不一樣的。為了描述此類情形，除了考慮以邊賦權圖為合作結構外，1988年， Meessen[6]提出圖博弈中另一個重要的分配規則, 也就是Position值。它是首先將圖博弈中的每條邊看成“參與者”,計算出每條邊的Shapley值[7], 然后把每條邊的Shapley值平均分配給它的兩個端點代表的參與者, 給每個參與者的支付(payoff)等于與它關聯的所有邊Shapley值一半的和。Borm等[8]給出了無圈圖博弈上Position值的唯一性刻畫，并討論了Position值的計算公式。van den Nouweland等[9]進一步把Position值推廣到超圖結構中,并把Borm等在無圈圖博弈上Position值的刻畫結果推廣到無圈超圖博弈上。2005年, Slikker[10]終于在任意圖博弈上證明了Position值能夠被分支有效公理和平衡邊貢獻(balanced link contributions)公理所唯一刻畫。2003年，Gómez等[4]在考慮社會網絡中心性和指數時，首次嘗試利用圖博弈中的Position值。最近，Belau[11]在Gómez等工作的基礎上，把圖博弈中Position值的概念推廣為廣義Position值作為衡量網絡中心性的標準，并討論了它的性質刻畫和應用。關于Position值的其他研究進展參見[12～14]。

近年來，超圖(hypergraph)作為超網絡的拓撲結構越來越受到關注。它是圖的一個自然推廣，在現實中是普遍存在的。例如，每個人可能會參加各種各樣的團體、協會和組織，這些人和國家可以看作參與者，而所在的團體、協會和組織可以看作超圖中的超邊(conference或者hyperlink)。不過，由于在超圖中，每個超邊由一些節點形成的子集所組成，不像圖中每條邊恰有兩個節點所形成，因此在超圖結構上的合作博弈其情形更加復雜。本文旨在推廣Belau[11]的思想，提出超圖博弈中的廣義Position值，這里稱為“υ-Position”值，并給出其公理化刻畫。從而為超網絡的中心性度量提供經濟意義上的理論方法。

本文的組織如下: 第二節給出超圖博弈的基本定義和記號。第三節提出超圖博弈υ-Position值的概念和新的公理——局部平衡超邊貢獻，并給出υ-Position值中“類Shapley-Position值”的公理化刻畫。最后舉例說明υ-Position值在超網絡中心性測度中的應用。

1 預備知識

1.1 TU-博弈

對于博弈(N,υ)，一個支付向量(payoff vector)x=(x1,x2,…,xn)∈Rn是指分配給第i個參與者的支付為xi。TU-博弈的單值解(single-valued solution)或者值(value)是一個映射f:VN→Rn,表示指派給每個(N,υ)的一個支付向量f(N,υ)∈Rn。這個值就是通常所說的分配規則(allocation rule)。對于給定的參與者集合N和一個非空聯盟T?N,一致性博弈(unanimity game)(N,uT)[7]定義為：若T?S,則有uT(S)=1；否則,有uT(S)=0。已經知道:任意一個博弈(N,υ)的特征函數都能唯一表示成一致性博弈的線性組合[15]，也即有

(1)

(2)

1.2 超圖和超圖博弈

作為圖的自然推廣，超圖(hypergraph)[9]由二元組(N,H)所組成,其中N表示節點的集合，H?HN={e?N:|e|≥2}表示至少含有兩個節點的超邊(hyperlink)集合。顯然，當每條超邊e滿足|e|=2時, 超圖即為普通的圖。如果N是明確的，通常用H代表超圖(N,H)。Hi為H中包含節點i的超邊的集合, 也即Hi={e∈H|i∈e}。節點i的度(degree)deg(i)定義為|Hi|。

在超圖H中,若i∈e,則稱節點i與超邊e∈H是關聯的;如果存在一條超邊e∈H滿足i,j∈e,則稱節點i和j是鄰接的。一條長度為k的路(path)是指一個點邊交替序列(i1,e1,i2,e2,…,ik,ek,ik+1),這里i1,i2,…,ik+1是不同的節點,e1,…,ek是H的不同超邊,且對每個1≤l≤k,il,il+1∈Hl。如果超圖H中任何兩個節點i,j之間均存在路,則稱H是連通的。對于任意非空集合S?N,(S,H(S)),稱為由節點集S導出的子超圖,其中H(S)={e∈H|e?S}。若H(S)是連通的，則稱S是H的一個連通子集。H的一個極大的連通子集稱為它的分支,記H所有分支的集合為N/H。 特別地，T/H(T)表示由T導出子超圖的分支集合。為了方便起見, 有時記T/H(T)為T/H。

超圖博弈(hypergraph game或者hypergraph communication situation)可以用一個三元組(N,υ,H)來表示,其中(N,υ)是一個TU-博弈，而(N,H)是一個超圖。此時，超圖的節點集N表示參與者的集合。H中每一條超邊e可表示一個conference結構[9]。在實際中,超邊可以代表某種社會組織如：行業協會、企業集團或者政治團體等,每個參與者可以參加多種行業組織或企業集團,并參與不同聯盟的合作。

以下分別記TU-博弈和超圖博弈分配規則的集合為A和AH。

1.3 超圖博弈的Position值

(3)

由于0-規范博弈與對應的非0-規范博弈具有策略等價性，同時為了避免計算的繁瑣，在以下的討論中，除非特別說明，涉及的博弈均指0-規范的TU-博弈。其他未定義的概念和記號可參考[18]。

2 υ-Position值

從1.3小節超圖博弈Position值的定義可知，Position值是借助超邊博弈的Shapley值定義的一類分配規則。事實上，我們這里也可以用其他值(如Banzhaf值[19])來替代(3)中的Shapley值，并得到相應的位置值。基于這個考慮，我們可以定義超圖博弈上的一類廣義Position值。

(4)

顯然，由定義可知：當v=Sh時，上述v-Position值即為普通的Position值。

正像前面指出的，在度量網絡中心性時，節點的度是考察其中心性的最基本方法之一。事實上，我們可以通過定義“權度”，將這個方法推廣到賦權圖或者賦權超圖上。

按照上述定義，可以根據每個節點權度的大小來衡量該節點的中心性。事實上，在某種意義上，v-Position值可作為度測度的一個推廣。

命題1在超網絡節點的中心性度量中，v-Position值是一類“權度”測度。

為了深入討論和刻畫v-Position值，注意到Shapley值和Banzhaf值的共性，我們把討論的分配規則限制在類Shapley值的范圍內。把A中滿足下列幾個基本性質的分配規則集合記為A*，也即對每個v∈A*,滿足下列四個性質：

(ii)對稱性(S):若i,j∈N且對任意的S?N{i,j}滿足：υ(S∪{i})=υ(S∪{j}),此時稱i和j是對稱的，則vi(N,υ)=vj(N,υ);

(iii)啞元非相關性(NI):若i∈N且對任意的S?N{i}滿足:υ(S∪{i})=υ(S)，此時稱i為啞元，則有vi(N,υ)=0且對任意的i≠j∈N,vj(N,υ)=vj(N{i},υ);

(iv)單值性(U):v能被唯一確定。

我們已經知道，在合作博弈中，有許多值如Shapley值和Banzhaf值等均滿足上述性質。下面我們的討論主要集中在A*上進行。當v∈A*時，此時由于v-Position值是基于具有Shapley值和Banzhaf值共性的分配規則給出的，因此也把它稱為“類Shapley-Position值”。

3 “類Shapley-position值”的公理化刻畫

本節將給出超圖博弈上“類Shapley-Position值”的公理化刻畫。為了符號簡便，當參與者集合N明確時，經常書寫時省略N。

分支有效性是說每個分支內的所有參與者的支付之和等于該分支的效用，這個性質強調節點的貢獻。仿照此思想，為了強調圖博弈中邊的貢獻，Belau[11]提出了一個性質公理，被稱為分支超邊指數。這里把分支超邊指數性質推廣到超圖博弈上。

分支超邊指數(Component Hyperlink Power,簡記為CHP),假設v∈A，對任意的(N,υ,H)∈HN及任意的C∈N/H，若分配規則f∈AH滿足

(5)

則稱f具有對應于分配規則v的分支邊指數性質。

這個性質的含義是: 超圖博弈(N,υ,H)中，對某一分支的支付等于該分支中在分配規則v下所有超邊的支付之和。

根據定義可以證明下列結果:

引理1對于任意超圖博弈(N,υ,H)∈HN及v∈A,πv∈AH滿足分支超邊指數(CHP)性質。

證明假設C∈N/H，注意到每條超邊e恰好貢獻|e|個度，根據(4)可得:

從而得證。

則稱f滿足平衡超邊貢獻。

不過, 對超圖博弈中的Position值進行刻畫時，平衡超邊貢獻性質是失效的。需要用到下列“部分平衡超邊貢獻”性質[20]:

部分平衡超邊貢獻(partial balanced hyperlink contributions，簡記為PBHC):對任意超圖博弈(N,υ,H)∈HN和i,j∈N,若分配規則f∈AH滿足

(6)

則稱f具有部分平衡超邊貢獻性質。

部分平衡超邊貢獻性質可解釋為：去掉包含參與者i的每條超邊對參與者j收益的平均影響的和等于去掉包含參與者j的每條超邊對參與者i收益的平均影響的和。明顯的, 若將超圖(N,H)限制為一般圖(N,L)時, 局部平衡超邊貢獻公理即為平衡邊貢獻公理。

為了證明超圖博弈(N,υ,H)∈HN的v-Position值滿足分支超邊指數和局部平衡超邊貢獻這兩個公理, 首先, 根據一致性博弈, 給出以下引理。

證明因為每個博弈的特征函數都可以寫成其對應的一致性博弈的線性組合[18]。因此,對于超圖博弈(N,υ,H),對應的超邊博弈υN可以表示為:

(7)

首先，注意到對每個e∈HK及任意T?H{e}，有uK(T∪{e})=uK(T)，因此e是一個啞元。所以對每個e∈HK，ve(H,λK(υN)uK)=0。因為v∈A*，由v值的性質NI可知：ve(H,λK(υN)uK)=ve(K,λK(υN)uK)。其次，注意到對任意的e,e′∈K及T?K{e,e′}，有uK(T∪{e})=uK(T∪{e′})=0,也即e和e′是對稱的，則由v值的性質S可知：對任意的e,e′∈K，有ve(K,λK(υN)uK)=ve′(K,λK(υN)uK),或者等價于，對任意的e∈K，有ve(H,λK(υN)uK)=ve(K,λK(υN)uK)=c(υ,v,K),根據v值的對稱性S和單值性U，這里c(υ,v,K)∈R是一個只依賴于υ,v,K的常數。進一步，根據v值的可加性A及(7)，我們有

因此，我們有

其中Ki=K∩Hi。令Kj=K∩Hj，于是有，

現在給出本文的主要結論。

現在假設對任何超圖H，當|H|

根據上式，對分支C內的所有節點做和，則得

(8)

因為φ滿足CHP性質，因此根據引理1，由(8)式的左邊可得：

(9)

同理，由(8)式的右邊可得：

(10)

4 υ-Position值在超網絡中心性測度中的應用舉例

本節通過Shapley-position值和Banzhaf-position值，舉例說明v-Position值的性質和它在超網絡中心性測度中的應用。

例1某經濟網絡，其經濟學模型可抽象為超網絡博弈(N,υ,H)∈HN，其中參與者集合為N={1,2,…,9},超邊集為H={{1,2,3},{3,4,5},{5,6,1},{2,4,6},{6,7,8},{8,9}},特征函數為υ=uN，如圖1所示。設e1={1,2,3},e2={3,4,5},e3={5,6,1},e4={2,4,6},e5={6,7,8},e6={8,9}。

圖1 超圖(N,H)

(11)

(12)

我們驗證Shapley-position值和Banzhaf-position值分別滿足性質CHP和PBHC。注意到超圖H是連通的，也就是恰好只有一個分支。由上面的計算結果，容易驗證:

因此這兩個值滿足部分平衡超邊貢獻性質。

下面分析Shapley-position值和Banzhaf-position值在度量超網絡H節點中心性時的一些特點。由超圖H的結構，容易計算各個參與者的度值分別為:

deg(i)=2,i=1,2,…,5,8

deg(6)=3;deg(7)=deg(9)=1

(13)

根據(11)～(13)式可得表1。

表1 各個參與者在三個值中所占的比例.

由表1，我們發現用度值來度量時，其度值最大的為參與者6，也就是參與者6在位于最中心的位置或者說為“top關鍵節點”，其次度值相對較大的是參與者1，2，…，5，8，它們為可看作“次關鍵節點”，而參與者7和9為最不重要的節點。

不過，在用Shapley-position值和Banzhaf-position值進行度量時，情況發生了很大變化。此時，參與者8的值最大，它成為“top關鍵節點”，而參與者6為“次關鍵節點”，而且參與者6在這兩個值中具有相同的比例值，也就是說中心性相同。在Shapley-position值中，參與者1,2,…,5成為最不重要的節點，而在Banzhaf-position值中，參與者7成為最不重要的節點。注意到參與者9在Shapley-position值測度中，其中心性提高顯著。其原因是在用Shapley-position值和Banzhaf-position值進行度量時，凸顯了超邊e5,e6作為中介的重要性，因為它們的任意一條被刪掉，網絡的連通性立即被破壞，而刪掉其他超邊e1,e2,e3,e4其中一條時，網絡仍保持連通。所以Shapley-position值和Banzhaf-position值測度體現了“超邊”作為橋梁的作用，而不是僅考慮節點的結構位置關系。

在現實生活中，選擇不同的分配方法，可以體現決策者不同的分配意圖。例如，在企事業單位內部的績效獎金分配過程中，決策者如果單純從某個部門或個人聯系面的廣泛性入手進行分配，那么那些交際面廣泛、在公共關系中發揮較大作用的部門或個人就能夠獲得較多的績效分配；但是，如果從單位內部整體運轉的不可或缺性著手，那么在整個部門協同機制中發揮關鍵連通作用的部門將獲得較多的績效分配。從績效獎金分配推而廣之，這三種不同的分配方法還能夠廣泛用于資產、資源的評估過程，因為資產或資源的評估建立在標準的價值計算模型上，而任何價值計算都有一定經濟學意義上的“偏向性”，因此，在評估時選取何種分配方法進行計算，將顯著體現出評估的目的取向性——是偏重于資產或資源的位置值還是偏重于它們的戰略地位，從而計算得出的價值是不同的。

5 結論及注記

本文討論了超網絡中心性測度的一類方法——廣義Position值(v-Position值)方法，用此類方法來度量時，既突出了“超邊的經濟作用”，又考慮了其結構關系，而傳統的度值等方法主要從節點所處的位置來考慮。另外，通過分支超邊指數和部分平衡超邊貢獻兩個性質，給出了類Shapley-position值的唯一性刻畫。注意到網絡博弈(圖博弈)是一類特殊的超圖博弈，此時每條邊恰有兩個元素，這導致在圖博弈中部分平衡超邊貢獻性質會退化為平衡邊貢獻性質，因此本文結果蘊含了一般網絡上的相關結論。在超網絡博弈中，當一條超邊被增加或者刪掉時，是否每個參與者都會受益或者受損？這就是超邊單調性問題，該問題對合作的穩定性具有重要影響。一般來說，這個問題的答案是否定的。那么到底超網絡博弈滿足什么條件就具有超邊單調性是需要進一步深入研究的問題。