有向加權網絡的重要模體識別及其應用

摘要： 為識別有向加權網絡中的重要加權模體，采用邊權定性為強弱標簽的方式將有向加權網絡轉換為標簽網絡、簡單模體拓展至標簽模體。對于三節(jié)點的標簽模體類型，用模體在隨機網絡中出現(xiàn)相應次數(shù)的概率估計值代替模體遍歷的含時過程，引入與標簽模體類型相關聯(lián)的動態(tài)指標識別出有向加權網絡中的重要標簽模體。將其應用到中國籃球職業(yè)聯(lián)賽（CBA）2019—2020賽季總決賽廣東隊、遼寧隊的傳球網絡，獲得球隊在比賽中出現(xiàn)的重要傳球模式及構成相應傳球模式的重要球員。重要標簽模體的識別對挖掘有向加權網絡的重要構建模式、關鍵節(jié)點有著顯著作用。

關鍵詞： 有向加權網絡；標簽網絡；標簽模體；籃球傳球網絡；運動表現(xiàn)分析

中圖分類號： TP391；N94文獻標識碼： A

Identification of Important Motifs in Directed Weighted Networks and Its Application

HOU Ximei， WANG Gaoxia， YANG Fan， WANG Yike

（a. College of Science ; b. Mathematics Research Center， China Three Gorges University， Yichang 443002， China）

Abstract：In order to identify the important weighted motifs in the directed weighted networks， the directed weighted networks are transformed into label networks and the simple motifs are expanded to label motifs by defining the edge weights as strong and weak labels. For the label motifs of the three nodes， the time-consuming procedure of subgraph traversal is replaced by the estimated probability of the corresponding number of the motifs appear in the random networks， and the important label motifs in the directed weighted networks are identified by introducing a dynamic indicator associated with the label motif type. It is applied to the passing networks of Guangdong team and Liaoning team in the 2019—2020 finals of China Basketball Association （CBA）. The important passing modes of the teams in the games and the important players in the corresponding modes are obtained. The important label motifs play a significant role in mining the important construction patterns and key nodes of the directed weighted networks.

Keywords： directed weighted networks; label networks; label motifs; basketball passing networks; sports performance analysis

0 引言

網絡是對系統(tǒng)的抽象描述方式，任何包含大量組成單元的系統(tǒng)都可以將構成單元抽象為節(jié)點，單元間的相互關系抽象為邊，從而建立網絡模型來研究。作為一個揭示網絡結構性質的有用概念，模體受到了廣泛的關注。Milo等［1］首次提出模體的概念，認為模體是節(jié)點互聯(lián)模式，并且數(shù)量明顯高于相同度序列下隨機網絡中的對應模式。Sporns等［2］基于大腦網絡提出了功能模體的概念，將網絡局部連通模式下的子圖看作功能模體。Benson等［3］對模體的定義進行了拓展，將有向無權網絡的連通子圖定義為簡單模體，同時給出了以特定節(jié)點（組）為中心的錨模體定義。模體能從局部層次刻畫網絡內部相互連接的特定模式，反映網絡的一些功能，在生物［45］、交通［6］、社會［7］等眾多領域有著廣泛應用。

模體的引入也將節(jié)點、節(jié)點組的重要性識別問題［89］擴展至重要模體識別問題。對于有向加權網絡，模體的定義及識別尚處于探索階段。一種簡單的處理方法是將加權網絡視為無權網絡，進行簡單模體的識別與分析。網絡的邊權反映了節(jié)點間結構的強弱性，將簡單模體推廣至加權模體能更好地反映加權網絡的局部特性。在模體加權的研究方面，一種方式是對簡單模體的整體結構進行加權處理，即通過引入模體邊權的平均值［10］、熵值［11］等，將加權模體定義為擁有整體權值的簡單模體。另一種方式是直接對簡單模體的邊賦權來定義加權模體。Li等［12］將邊權定性為兩類進行加權模體識別并用此方法進行用戶產品評價的真實性研究［13］和經典戲劇的創(chuàng)作模式研究［14］。Shen等［15］提出了尋找微生物網絡中最優(yōu)加權模體的方法，并分析了加權網絡的高階結構。Picciolo等［16］基于固定最大步數(shù)的隨機游走研究有限大小的加權模體。本文基于文獻［12］引入一個新的分段函數(shù)將有向加權網絡的邊權映射為強弱標簽進而將構成網絡的加權子圖轉換為標簽模體，并給出了三節(jié)點標簽模體的類型數(shù)目及其表示方法。在不枚舉零模型的前提下，估計出標簽模體在對應隨機網絡中生成相應次數(shù)的概率，并考慮與標簽模體類型相關聯(lián)的動態(tài)指標識別出重要的標簽模體類型。

在應用領域，通過社會網絡對團隊運動表現(xiàn)進行分析是一個新興現(xiàn)象，相關研究呈現(xiàn)快速發(fā)展的趨勢［17］。球類運動中，球員之間的配合通過傳接球關系反映在網絡的模體結構中，文獻［18］識別出足球傳球網絡中頻繁出現(xiàn)的模體類型，據此分析球隊常用的傳球路線，利用模體頻率的相關性衡量出兩支球隊的實力強弱。文獻［19］利用模體的研究方法分析了土耳其國家籃球隊在歐洲籃球錦標賽上的籃球技戰(zhàn)術。上述與模體相關的研究是將傳球網絡視為有向無權網絡來識別重要模體，而忽略了權重（球員間傳球頻次）這一重要因素，實際比賽過程中球員間往往存在多次傳球，基于有向加權網絡進行相關模體研究更符合實際情況。三節(jié)點網絡模體與籃球傳球技戰(zhàn)術有密切的聯(lián)系，而國內相關研究較少，故本文收集2019—2020賽季CBA總決賽廣東隊、遼寧隊的傳球數(shù)據，將兩支球隊球員之間的傳球關系構建成有向加權網絡模型，根據提出的重要標簽模體識別方法識別出籃球傳球網絡中球隊球員間重要的傳球模式，并以廣東隊為例分析相關傳球模式下的關鍵球員。

1 標簽模體及其表示

簡單模體可看作有向無權網絡中連通的子圖形式，其中3個節(jié)點的簡單模體類型共有13種［3］，如圖1所示，分別用Mj表示，j=1，…，13。

將有向加權網絡中每一條有向邊的權值賦予二元標簽，定性表示節(jié)點間交聯(lián)程度的強弱，從而可將簡單模體拓展至標簽模體。標簽分為兩類：強標簽S和弱標簽W。賦予強弱標簽后，每一種簡單模體對應了多種不同構的標簽模體，基于M1至M13的標簽模體類型分別有4，16，32，16，8，10，10，3，4，3，8，8，10種，共132種。圖2展示了基于簡單模體M1的所有標簽模體類型。

對簡單模體類型Mj，將構成標簽模體的強弱標簽個數(shù)分別用SC、WC表示進而對具體標簽模體類型命名，其格式為MjSCWCk（n），其中，j=j∈N+1≤j≤13，k代表在同種簡單模體Mj下，擁有相同強弱標簽數(shù)的不同標簽模體類型數(shù)目，n代表在k種模體下的第n種模體類型（1≤n≤k）。例如簡單模體M2，共有4條有向邊，按強弱標簽的個數(shù)分別對應SC=4，WC=0；SC=3，WC=1；SC=2，WC=2；SC=1，WC=3；SC=0，WC=4五種情形，根據強弱標簽在M2中的位置，具有相同的強弱標簽數(shù)又對應著不同的標簽模體類型，分別為1，4，6，4，1種。圖3展示了基于M2且強弱標簽個數(shù)分別為3，1的所有標簽模體類型，這4種模體基于相同的簡單模體，具有相同的強弱標簽數(shù)，不同的是強弱標簽在模體中的位置，位置的不同利用n值進行區(qū)分，分別表示為M2314（1），M2314（2），M2314（3），M2314（4）。當同種簡單模體下只出現(xiàn)一種擁有指定強弱標簽數(shù)的模體時，k取1，標簽模體可寫成MjSCWC1的形式，例如圖2中顯示的M1對應的標簽模體類型。

2 重要標簽模體識別

2.1 邊標簽的確定

標簽模體可看作有向加權網絡對應下的標簽網絡的連通子圖，模體邊標簽的確定可以轉換到有向加權網絡邊標簽確定的問題上。

首先，將有向加權網絡G的邊權映射到0，1區(qū)間。考慮有向加權網絡的所有鏈接L，用xi表示網絡第i條邊的權值，則平均邊權為μ=1L∑Li=1xi，將滿足xi≤μ的有向邊中的最小邊權、最大邊權用xmin，xmax表示，定義函數(shù)u（x）

u（x）=x－xmin+1xmax－xmin+1，x∈0，μ1，x∈μ，+∞（1）

其中，x代表網絡的邊權，函數(shù)u（x）將網絡的邊權映射到0，1區(qū)間。把邊權映射到0，1區(qū)間，而不是0，1區(qū)間，是因為當邊權變換成0時，易與不連通的兩個節(jié)點構成的0邊權（鄰接矩陣的零元素）混淆。通過對分子分母添加常數(shù)1，來達到當x=xmin時，u（x）≠0的目的。

其次，對處理后的邊權，選取恰當?shù)拈撝祵崿F(xiàn)邊權到強弱標簽的轉換。將在閾值之上（包含閾值）的邊權值變換成強權標簽，閾值之下的邊權值變換成弱權標簽。根據最大似然估計方法，閾值θ范圍［12］為0.5，1，這里取區(qū)間的中間值0.75為閾值。通過這種方式確定了有向加權網絡的邊標簽，對應網絡轉變成了標簽網絡，相應可得到有向加權網絡G的標簽模體類型。

2.2 重要標簽模體識別標準

每一種標簽模體的結構、出現(xiàn)次數(shù)不同，其重要性也不盡相同。重要模體是指在隨機網絡中模體出現(xiàn)次數(shù)大于或等于在實際網絡中出現(xiàn)次數(shù)的概率低于截斷值的模式［1］。截斷值越小越能顯示模體的重要性。對于實際網絡對應下的隨機網絡，其轉化為標簽網絡后要與實際網絡的強弱標簽數(shù)相同。對于一個實際標簽網絡，統(tǒng)計出標簽模體在網絡中出現(xiàn)的次數(shù)，用下面的方法估計模體在隨機網絡中出現(xiàn)次數(shù)大于或等于在實際網絡中出現(xiàn)次數(shù)的概率。

如Picardetal等所示［20］，可將標簽模體M在隨機有向標簽網絡中出現(xiàn)一次的概率看作

P1M=Pr{Y（M）=1}=∏u，v∈γMu≠vπuv（2）

其中，γM為構成標簽模體M的節(jié)點集，πuv為節(jié)點u指向節(jié)點v的連接概率。則標簽模體在隨機標簽網絡出現(xiàn)z次的概率PzM=Pr{Y（M）=z}可表示為（P1M）z，當P1M等于0或等于1時，PzM為定值；當P1M大于零且小于1時，PzM隨著z的增大而遞減，則“模體在隨機網絡中出現(xiàn)次數(shù)大于在實際網絡中出現(xiàn)次數(shù)”的概率小于等于“模體在隨機網絡中出現(xiàn)次數(shù)等于在實際網絡中出現(xiàn)次數(shù)”的概率。因此識別重要標簽模體只需比較模體在隨機網絡中出現(xiàn)次數(shù)等于在實際網絡中出現(xiàn)次數(shù)的概率與截斷值的大小。

用ES，EW分別表示實際標簽網絡中強標簽和弱標簽數(shù)（ES+EW=L），強標簽的概率表示為PS=ES/L，弱標簽的概率表示為PW=EW/L。由于設定隨機網絡轉化為標簽網絡后要與實際網絡的強弱標簽數(shù)相同，ES，EW，PS，PW同時適用于對應的隨機網絡。對于一個具有SC個強標簽和WC個弱標簽的標簽模體MjSCWCk（n），假設其在實際網絡中出現(xiàn)的次數(shù)為EM，則“模體在隨機網絡中出現(xiàn)次數(shù)=在實際網絡中出現(xiàn)次數(shù)”的概率PEMM滿足：

PEMM=（∏1≤u，v≤γMu≠vπuv）EM≤（（PS）SC·（PW）WC）EM（3）

其中，（PS）SC·（PW）WC可看作在對應隨機網絡中選擇SC條強標簽的邊，WC條弱標簽的邊的概率，它包含著標簽模體MjSCWCk（n）出現(xiàn)一次的情況，故式（3）成立，則可通過（（PS）SC·（PW）WC）EM是否滿足低于截斷值判斷模體的重要性。由于考慮的是有向標簽模體，截斷值應隨著模體類型變化而變化，本文將截斷值設置為0.1SC+WC，其隨著模體類型中的強弱標簽數(shù)（SC，WC）而變化。則將模體在隨機網絡中出現(xiàn)次數(shù)大于或等于在實際網絡中出現(xiàn)次數(shù)的概率小于0.1SC+WC的類型看作為重要標簽模體。

3 籃球傳球網絡分析

3.1 傳球網絡模型的建立

籃球作為中國三大球之一，其研究具有一定的意義，本文選取2019—2020賽季CBA總決賽雙方球隊的傳球數(shù)據為樣本進行分析。比賽對戰(zhàn)雙方是廣東隊和遼寧隊，比賽采取三局兩勝制。三場比賽兩隊的比分分別是110∶88，113∶115，123∶115。廣東隊以2∶1贏得比賽，成為2019—2020年度CBA總決賽的冠軍。通過查詢相關網站、回看比賽視頻進行信息收集和處理進而構建廣東隊、遼寧隊的籃球傳球網絡模型。具體步驟如下：

第1步，通過中國男子籃球職業(yè)聯(lián)賽官方網站（http：//www.cbaleague.com/），獲取兩支球隊上場的球員姓名及代表球員的球衣號碼（見表1）。

第2步，觀看相關視頻，記錄廣東隊、遼寧隊各場比賽出場的陣容及相關陣容下球員間的傳球路線（包括重復傳球，其中三場比賽中廣東隊共有924次傳球，分別為279次、333次、312次，遼寧隊共存在925次傳球，分別為321次、305次、299次）。

第3步，將三場比賽收集到的兩隊球員間的傳球路線轉換成網絡文件的格式以進行后續(xù)計算與分析。

將網絡文件可視化，得到了三場比賽兩隊球員間的傳球網絡圖。圖4顯示了廣東隊、遼寧隊第一場比賽G1，L1的傳球網絡圖，用球員球衣號碼代表比賽中出場的球隊球員，箭頭的方向代表球員間傳球的方向，箭頭的大小，邊的粗細與球員間傳球次數(shù)的多少相對應。

3.2 傳球網絡的重要標簽模體識別

在籃球傳球網絡中，強弱標簽是對球員間傳球相對頻繁程度的一種劃分，強標簽代表著球員間傳球相對頻繁，弱標簽意味著球員間傳球互動相對較弱。根據2.1將三場比賽兩隊傳球網絡的邊權變換成強弱標簽，其中兩隊第一場比賽情況如圖5所示，統(tǒng)計標簽網絡中的強弱標簽數(shù)，出現(xiàn)的標簽模體類型及次數(shù)。對于出現(xiàn)的標簽模體類型，分別計算模體對應下的（（PS）SC·（PW）WC）EM值和截斷值0.1SC+WC，將低于截斷值的相應標簽模體看作對應球隊傳球網絡的重要標簽模體。針對每場比賽可找到廣東隊、遼寧隊的重要標簽模體類型，結果詳見圖6，GmMjSCWCk（n）、LmMjSCWCk（n）分別代表廣東隊、遼寧隊的第m場比賽下的重要標簽模體類型（m=1，2，3）。

圖6得到的重要標簽模體類型分別代表著比賽過程中各自球隊球員傳球頻繁出現(xiàn)的子圖模式，可知悉每場比賽球員間傾向的傳球路線與傳球頻率強弱。從圖6可知，廣東隊（遼寧隊）在三場比賽的傳球網絡中共出現(xiàn)31（21）種重要標簽模體，排除遼寧隊（廣東隊）同時包含的重要標簽模體，還有23（14）種。相比之下，廣東隊的傳球模式更多樣，球員配合傳球方式更靈活，更易打破壁壘，創(chuàng)造投籃機會。

將兩支球隊同時出現(xiàn)在三場比賽中的重要標簽模體類型進行對比，其中M4511，M13224（1）模體為共同出現(xiàn)在廣東隊三場比賽中且沒有共同出現(xiàn)在遼寧隊三場比賽中的重要標簽模體，M4601模體為共同出現(xiàn)在遼寧隊三場比賽中且沒有共同出現(xiàn)在廣東隊三場比賽中的重要標簽模體。從模體整體結構上看，這三種模體至少存在互聯(lián)的兩對節(jié)點對，且構成模體的互惠邊更傾向于標簽強弱程度相同，說明球在節(jié)點間存在多次均衡的傳遞流動，球員間傳球關系相對穩(wěn)定。

3.3 廣東隊重要標簽模體下的球員分析

由于廣東隊歷年來奪冠次數(shù)最多，下面以廣東隊為研究對象，分析其球隊在重要傳球模式M4511，M13224（1）下的球員構成。

根據重要標簽模體（M4511，M13224（1））的結構及邊權標簽，考慮利用模體中存在的相同互惠關系來識別構成相應模體的重要節(jié)點（圖7白色節(jié)點）。標簽模體中相同的互惠關系結構意味著球員間傳球次數(shù)相當，球員實力相當，即構成的傳球關系相對穩(wěn)定，不易被對手打破。

統(tǒng)計構成廣東隊傳球模式M4511，M13224（1）的球員組合（見表2）并記錄重要節(jié)點代表的球員（表2中黑色加粗號碼），統(tǒng)計其出現(xiàn)的次數(shù)，識別出對應傳球模式下的關鍵球員，即10號球員是構成模體M4511的重要球員；13號球員是構成模體M13224（1）的重要球員。

由于球員的角色不同，其在比賽中的任務不同，構成傳球網絡的局部結構也不同。后衛(wèi)（控球后衛(wèi)、得分后衛(wèi)）指組織進攻，協(xié)調防守，回防迅速的球員，大前鋒是主要負責防守的球員，小前鋒是球隊中最重要的得分者，擅長較遠距離的得分，中鋒強調籃下的防守以及防守籃板球的保護。由于本文考慮的傳球網絡由球員的進攻傳球構成，傳球模式應主要圍繞著后衛(wèi)、小前鋒，從得到的關鍵球員角色得以驗證。

模體中的關鍵節(jié)點代表著比賽中發(fā)揮著重要作用的球員，球員的重要性體現(xiàn)在得分上，包括自己投籃得分，助攻隊友得分兩方面。從CBA網站廣東隊球員在三場比賽的總戰(zhàn)績情況（見表3）可知，結論得到的關鍵球員中10號球員是后衛(wèi)，且其平均得分、助攻次數(shù)同時相對較高；對于上場的小前鋒，13號球員的平均得分最高、助攻次數(shù)也相對較高，故可稱他們?yōu)橄鄳獋髑蚪Y構下的關鍵球員，得到的結論具有可信性。

4 結論

在有向加權網絡中，本文將網絡的邊權處理為對應節(jié)點間聯(lián)系強弱的標簽，通過對比模體在隨機網絡中出現(xiàn)次數(shù)大于或等于在實際網絡中出現(xiàn)次數(shù)的概率和截斷值的大小確定重要標簽模體類型。將其應用到CBA傳球網絡，得到了比賽過程中球隊球員傳球頻繁出現(xiàn)的子圖模式。以廣東隊為例，針對不同于對手球隊的傳球模式，識別出球隊在相應傳球模式下的關鍵球員。對于教練而言，熟知球員熟悉的傳球模式，加以利用，可增加投籃命中率，更有機會贏得比賽。

同時，只要所研究的實際網絡背景下模體結構具有特定的意義，原則上都可采用該方法識別出其它有向加權網絡的重要標簽模體類型。本文針對的是三節(jié)點模體下的重要標簽模體識別，對于更高階的模體模式將在今后的工作中進一步研究，并將其推廣應用到更廣泛的領域。

參考文獻：

［1］MILO R， SHEN-ORR S， ITZKOVITZ S， et al. Network motifs： simple building blocks of complex networks［J］. Science， 2002， 298（5594）： 824827.

［2］SPORNS O， KTTER R， FRISTON K J. Motifs in brain networks［J］. PLoS Biology， 2004， 2（11）： e369.

［3］BENSON A R， GLEICH D F， LESKOVEC J. Higherorder organization of complex networks［J］. Science， 2016， 353（6295）： 163166.

［4］SHENORR S S， MILO R， MANGAN S， et al. Network motifs in the transcriptional regulation network of Escherichia coli［J］. Nature Genetics， 2002， 31（1）： 6468.

［5］DOBRIN R， BEG Q K， BARAB SI A L， et al. Aggregation of topological motifs in the Escherichia coli transcriptional regulatory network［J］. BMC Bioinformatics， 2004， 5（1）： 18.

［6］JIN Y， WEI Y， XIU C， et al. Study on structural characteristics of China′s passenger airline network based on network motifs analysis［J］. Sustainability， 2019， 11（9）： 2484.

［7］賈承豐， 韓華， 完顏娟， 等. 基于網絡模體特征攻擊的網絡抗毀性研究［J］. 復雜系統(tǒng)與復雜性科學， 2019， 14（4）： 4350.

JIA C F， HAN H， WAN Y J， et al. Network destruction resistance based on network motif feature［J］. Complex Systems and Complexity Science， 2019， 14（4）： 4350.

［8］LIU H， XU X， LU J A， et al. Optimizing pinning control of complex dynamical networks based on spectral properties of grounded Laplacian matrices［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2018， 51（2）： 786796.

［9］劉慧， 王炳珺， 陸君安， 等. 復雜網絡牽制控制優(yōu)化選點算法及節(jié)點組重要性排序［J］. 物理學報， 2021， 70（5）： 284.

LIU H， WANG B J， LU J A， et al. Nodeset importance and optimization algorithm of nodes selection in complex networks based on pinning control［J］. Acta Physica Sinica， 2021， 70（5）： 284.

［10］ ONNELA J P， SARAMKI J， KERTSZ J， et al. Intensity and coherence of motifs in weighted complex networks［J］. Physical Review E， 2005， 71（6）： 065103.

［11］ CHOOBDAR S， RIBEIRO P， SILVA F. Motif mining in weighted networks［C］∥2012 IEEE 12th International Conference on Data Mining Workshops. Brussels， Belgium： IEEE， 2012： 210217.

［12］ LI J， YANG D， JI C. Mine weighted network motifs via Bayes′ Theorem［C］∥2017 4th International Conference on Systems and Informatics （ICSAI）. Hangzhou， China： IEEE， 2017： 448452.

［13］ LI J， LV P， JI C. Uncover product review patterns via weighted motifs［C］∥2018 5th International Conference on Systems and Informatics （ICSAI）. Nanjing， China： IEEE， 2018： 445448.

［14］ LI J， YANG D， LV P. Visualize classic play′s composing patterns： a weighted motif mining framework［J］. Multimedia Tools and Applications， 2019， 78（5）： 59896012.

［15］ SHEN X， GONG X， JIANG X， et al. Highorder organization of weighted microbial interaction network［C］//2018 IEEE International Conference on Bioinformatics and Biomedicine （BIBM）. Madrid， Spain： IEEE， 2018： 206209.

［16］ PICCIOLO F， RUZZENENTI F， HOLME P， et al. Weighted network motifs as random walk patterns［J］. New Journal of Physics， 2022， 24（5）： 053056.

［17］ 張巖， 楊改生. 社會網絡分析在團隊運動表現(xiàn)中的應用：研究綜述［J］. 中國體育科技， 2022， 58（1）： 100108.

ZHANG Y， YANG G S. The application of social network analysis in team sports performance：a review［J］. China Sport Science and Technology， 2022， 58（1）： 100108.

［18］ HLAND E M， WIIG A S， HVATTUM L M， et al. Evaluating the effectiveness of different network flow motifs in association football［J］. Journal of Quantitative Analysis in Sports， 2020， 16（4）： 311323.

［19］ OBANOGˇLU H O. Using of network motifs on basketball tactical analysis［J］. Journal of Education and Training Studies， 2019， 7（3S）： 6270.

［20］ PICARD F， DAUDIN J J， KOSKAS M， et al. Assessing the exceptionality of network motifs［J］. Journal of Computational Biology， 2008， 15（1）： 120.

（責任編輯 李 進）