譚桂敏,汪麗娜,2,臧臣瑞
(1.內蒙古工業(yè)大學理學院,呼和浩特 010051;2.內蒙古生命數(shù)據(jù)統(tǒng)計分析理論與神經(jīng)網(wǎng)絡建模重點實驗室,呼和浩特 010051;3.中國聯(lián)合網(wǎng)絡通信有限公司內蒙古分公司,呼和浩特 010050)
各個領域都蘊藏了豐富的時空數(shù)據(jù)。隨著傳感器和通信技術的快速發(fā)展,累積了大量包含地理位置信息的時空數(shù)據(jù)。越來越多的科學家關注時空數(shù)據(jù)的信息挖掘。與關系數(shù)據(jù)不同,時空數(shù)據(jù)除了具有實體及實體之間的聯(lián)系屬性,還包含了時間屬性和空間屬性[1]。時空屬性的存在為分析數(shù)據(jù)帶來了挑戰(zhàn)。
二分網(wǎng)絡可以展示兩類不同屬性群組成員之間的聯(lián)系,如電影演員網(wǎng)絡中,演員演出電影關系由演員群組與電影群組中節(jié)點間的連邊表示?,F(xiàn)實中存在大量不同屬性群組之間的交互關系,利用二分網(wǎng)絡可以研究不同群組間交互關系的特征。二分網(wǎng)絡投影成單分網(wǎng)絡能夠提取二分網(wǎng)絡中的隱含信息,研究同類節(jié)點之間直接的聯(lián)系。在互聯(lián)網(wǎng)應用領域,惡意域與客戶端[2]、用戶與應用程序[3]、用戶與網(wǎng)頁[4]、編碼器與接收器[5]等存在聯(lián)系。根據(jù)網(wǎng)絡流量日志中存儲的網(wǎng)絡犯罪信息,Jeng等[2]構造了惡意域與客戶端二分網(wǎng)絡,分析網(wǎng)絡特征發(fā)現(xiàn)了其他無法識別的威脅情報系統(tǒng)的新惡意域。Zhang等[3]把用戶的偏好關系表達成用戶與音樂的二分網(wǎng)絡,提出了一種改進的二分圖鏈接預測音樂推薦方法。在醫(yī)學領域,藥物與靶細胞[6],藥物與蛋白質[7]、基因組與連接體[8]等存在關聯(lián)關系。Manoochehri等[6]構建藥物與靶細胞二分網(wǎng)絡,研究藥物與靶細胞之間的潛在相互作用。Wang等[7]構建藥物與蛋白質二分網(wǎng)絡,挖掘藥物疾病相互作用以理解潛在的生物機制。在學術研究領域,郗強等[9]以領域和關鍵詞、學者和領域、作者和機構3個二分網(wǎng)絡分析了焦點、作者、機構與領域之間的關系。
目前,人們主要研究源于現(xiàn)實的兩類群組中自然存在的關系,如演員—電影、學者—論文、用戶—網(wǎng)頁等。針對抽象的不同屬性的群組中基元之間聯(lián)系的研究比較少。比如,時空數(shù)據(jù)中的時間屬性可以抽象為時間節(jié)點;空間屬性可以抽象為空間節(jié)點,時空交互關系抽象為兩類節(jié)點之間的連邊,以構建二分網(wǎng)絡。由于考慮了時空數(shù)據(jù)中包含基元的時間和空間相互作用關系,二分網(wǎng)絡可以研究基元的時空演化特征。二分網(wǎng)絡投影成單分網(wǎng)絡,可以探討基元時間或空間的直接聯(lián)系。
上述時空數(shù)據(jù)建立二分網(wǎng)絡可以挖掘時空數(shù)據(jù)中的信息。除此之外,最近Yang等[10]提出了高斯核密度估計和滑動窗口相結合的方法來挖掘交通流時空數(shù)據(jù)中的關鍵道路。Jiang等[11]利用無監(jiān)督分布學習方法提高了空間和時間相關預測的準確性。Wang等[12]詳細挖掘在發(fā)生自然災害時,人類情緒的時空特征。Charakopoulos等[13]利用互相關分析和復雜網(wǎng)絡方法,提取隱藏的時空特征。時空聚類也是一種時空數(shù)據(jù)挖掘方法,可以發(fā)現(xiàn)基元之間的相似性。傳統(tǒng)的聚類方法并不適用于高維數(shù)據(jù)。傳統(tǒng)的時間序列聚類方法要么只考慮時間,不能保證得到的聚類群組在空間上是連續(xù)的[14];要么只考慮空間,不能確保不同的群組是不同的[15]。時空數(shù)據(jù)建立二分網(wǎng)絡的核心—邊緣聚類則可以綜合時間和空間信息,得到群組間差異最大的聚類結果。
移動通信領域所有基站可看作復雜系統(tǒng),使用復雜網(wǎng)絡方法是研究基站系統(tǒng)的一個新視角。Wang等[16]提出了一種新的時間序列建網(wǎng)方法。此方法可以體現(xiàn)移動通信業(yè)務量時間序列中單個值的細節(jié)變化。Wang等[17]用基于網(wǎng)絡理論的深度學習方法預測蜂窩數(shù)據(jù)流,預測結果優(yōu)于傳統(tǒng)的時間序列方法。Li等[18]通過將時間序列映射為復雜網(wǎng)絡,捕捉時間序列的局部特征。Enami等[19]提出了一種軌跡數(shù)據(jù)的挖掘和預測算法,在時空上預測用戶未來的移動性行為。從而預測流量需求,適當分配網(wǎng)絡資源。因此從海量的移動通信時間序列數(shù)據(jù)中發(fā)掘通信數(shù)據(jù)演化規(guī)律,應用于智能通信系統(tǒng)以及時應對突發(fā)流量激增的情況,可以提高網(wǎng)絡資源的利用率。
為探究移動通信基站流量的時空特征,本文建立了耦合網(wǎng)絡模型。利用核心—邊緣聚類方法,分析時空尺度上吞吐量和話務量的聚類特征。
二分網(wǎng)絡可以將時空數(shù)據(jù)一體化,研究時間與空間的相互作用關系。在本文移動通信基站時空數(shù)據(jù)的背景下,建網(wǎng)的具體過程為:
1)確定節(jié)點??臻g節(jié)點為所選區(qū)域內各個空間位置的基站,代表基站覆蓋范圍。時間節(jié)點為等長的時間序列片段。應用滑動相關法劃分時間序列,取時間窗口為24時,步長為1,得到時間序列片段,代表吞吐量和話務量時間序列動態(tài)變化特征(耦合過程)。
2)建立相似度矩陣。從時空序列矩陣出發(fā),計算任意一個基站上兩列時間序列片段的斯皮爾曼相關系數(shù),得相似度矩陣S
(1)
其中,元素sij≠sji,sij為時間段i內基站j上兩列時間序列之間的相似度即耦合程度。相似度矩陣是一個非對稱矩陣。
3)構建二分網(wǎng)絡。依據(jù)相似度和閾值σ確定節(jié)點間是否存在連邊。一般定義相似度r的絕對值|r|≥0.8為強相似。考慮到強相似代表耦合顯著,取閾值σ為0.8。如果某時間段內任意一個基站上兩列時間序列的相似度絕對值不小于閾值,則對應的時間節(jié)點和空間節(jié)點之間存在連邊;否則不存在連邊。即鄰接矩陣A中的元素aij為
(2)
其中,aij=1意味著時間節(jié)點i和空間節(jié)點j之間存在一條邊。此時,認為在時間節(jié)點i代表的時間段內空間節(jié)點j上的兩列時間序列具有高相似性,表明時間段i內基站j上的數(shù)據(jù)業(yè)務吞吐量和話音業(yè)務話務量耦合顯著。反之,aij=0意味著時間節(jié)點i和空間節(jié)點j之間不存在邊。此時,認為在時間節(jié)點i代表的時間段內空間節(jié)點j上的兩列時間序列不具有高相似性,表明時間段i內基站j上的數(shù)據(jù)業(yè)務吞吐量和話音業(yè)務話務量耦合不顯著。
在分析二分網(wǎng)絡時,通常將它投影成單分網(wǎng)絡,再分析單分網(wǎng)絡的拓撲性質。二分網(wǎng)絡中有兩類屬性不同的節(jié)點,因此可以投影得到兩個單分網(wǎng)絡。例如,在本文耦合二分網(wǎng)絡中,如果時間節(jié)點t1,t2都與某個空間節(jié)點s3相連,那么在對應的時間單分網(wǎng)絡中,t1,t2之間就存在一條連邊。類似地,如果空間節(jié)點s1,s2都與某個時間節(jié)點t2相連,那么在對應的空間單分網(wǎng)絡中,s1,s2之間就存在一條連邊。
上述無權的投影方法應用廣泛,但是它的構造方式使得原始二分網(wǎng)絡的一些信息丟失。比如,投影中并沒有保留兩個時間節(jié)點(空間節(jié)點)共同連接的空間節(jié)點(時間節(jié)點)的數(shù)量。通過給連邊賦予權重,可以彌補缺陷,在投影中保留這類信息。即如果時間節(jié)點t1,t2既與空間節(jié)點s3相連又與空間節(jié)點s5相連,那么在對應的時間單分網(wǎng)絡中t1,t2之間連邊的權重為2。本文中,把兩個時間節(jié)點(空間節(jié)點)共同連接的空間節(jié)點(時間節(jié)點)的個數(shù)作為權重,投影得到加權的單分網(wǎng)絡。
Borgatti和Everett[20-21]提出二分網(wǎng)絡的核心—邊緣結構模型,分析二分網(wǎng)絡的聚類特征。核心—邊緣結構模型是將鄰接矩陣的行和列聚類為兩類(核心、邊緣)的理想模型,聚類結果的主對角線上是兩個子塊。其中一個是高密度塊,稱之為核心;另一個是低密度塊,稱之為邊緣。核心—邊緣結構模型可以用來識別事件群聚群發(fā)的區(qū)域。本文的二分網(wǎng)絡聚類之后,核心區(qū)是時間和空間上頻繁發(fā)生的事件,邊緣區(qū)是時間和空間上發(fā)生頻率低的事件。核心—邊緣結構模型的聚類過程如圖1所示。
圖1 聚類流程圖Fig.1 The process diagram of clustering
以3個基站構成的系統(tǒng)為例說明建立二分網(wǎng)絡過程及投影成時間單分網(wǎng)絡和空間單分網(wǎng)絡過程。數(shù)據(jù)的時空序列矩陣Ds和Dh為
(3)
Ds中的3列分別對應3個基站上的吞吐量時間序列,Dh中的3列分別對應與Ds中相同的3個基站上的話務量時間序列。根據(jù)步驟1)中取時間窗口為24時,步長為1劃分得到時間序列片段。每列時間序列經(jīng)過劃分得到3個時間序列片段。分別計算每個基站上的兩列時間序列片段(吞吐量,話務量)之間的斯皮爾曼相關系數(shù),得相似度矩陣S為
(4)
根據(jù)步驟3選取閾值為0.8。根據(jù)公式(2),得二分網(wǎng)絡的鄰接矩陣A
(5)
二分網(wǎng)絡如圖2a所示,二分網(wǎng)絡的單模投影得到的時間網(wǎng)絡和空間網(wǎng)絡如圖2b,2c所示,圖中邊的粗細和權重成正比。二分網(wǎng)絡中t1通過s2與t2相連,也通過s3與t2相連,如圖2b所示時間網(wǎng)絡中t1和t2連邊權重為2。同樣的s2可以分別通過t1和t2與s3相連,如圖2c所示空間網(wǎng)絡中s2和s3連邊權重為2。
圖2 二分網(wǎng)絡及投影的單分網(wǎng)絡Fig.2 Bipartite network and corresponding unipartite network
對如上二分網(wǎng)絡做核心邊緣結構分析,聚類后的分塊矩陣為
(6)
核心區(qū)為時間節(jié)點t1和t3和空間節(jié)點s3,說明s3基站在t1和t3時刻發(fā)生耦合事件次數(shù)多。邊緣區(qū)為時間節(jié)點t2和空間節(jié)點s1和s2,說明s1和s2基站在t2時刻發(fā)生的耦合事件的次數(shù)少。密度矩陣如式(7)所示,主對角線上核心區(qū)密度為1,邊緣區(qū)密度為0。
(7)
本文所選數(shù)據(jù)為某市運營商提供的基站自動采集的數(shù)據(jù)。從2017年2月22日0:00至2月26日18:00,近90 000條數(shù)據(jù)。每條數(shù)據(jù)是一個具有三維屬性(時間屬性、空間屬性、流量屬性)的五維向量(時間,經(jīng)度,緯度,數(shù)據(jù)業(yè)務吞吐量,話音業(yè)務話務量),表示某時某地理位置處的基站,其覆蓋范圍內的吞吐量和話務量。預處理后得到116個基站上的吞吐量與話務量時間序列,每個時間序列的長度為139。
首先,將時空數(shù)據(jù)一體化,建立一個耦合二分網(wǎng)絡。其中利用斯皮爾曼相關系數(shù)度量吞吐量和話務量時間序列的耦合是否顯著,耦合顯著則稱某基站在某時間段內發(fā)生了耦合事件。再將耦合二分網(wǎng)絡投影成時間單分網(wǎng)絡和空間單分網(wǎng)絡,分析拓撲性質。
本文所建的耦合二分網(wǎng)絡代表3種情況:1)不同時間段內的耦合事件發(fā)生在不同的基站;2)多個耦合事件發(fā)生在同一個基站;3)在同一個時期內,耦合事件發(fā)生在多個基站。耦合二分網(wǎng)絡可以反應耦合事件的動態(tài)演化過程,吞吐量與話務量耦合可以反映多種事件的疊加效應。耦合二分網(wǎng)絡有116個時間節(jié)點,116個空間節(jié)點。其中空間節(jié)點中存在42個孤立節(jié)點,表示其對應的基站上無耦合事件發(fā)生,本文不分析孤立節(jié)點。稱耦合二分網(wǎng)絡的最大連通子圖為C網(wǎng)絡(Coupling Network),如圖3所示,C網(wǎng)絡中有116個時間節(jié)點,74個空間節(jié)點。
圖3 C網(wǎng)絡Fig.3 C network
藍色正方形代表空間節(jié)點,即基站,紅色圓點代表時間節(jié)點即不同的時間段。空間節(jié)點可以分為兩類:圖3中外圍藍色空間節(jié)點和中心綠色空間節(jié)點。綠色空間節(jié)點上的連邊數(shù)均超過50,大于藍色節(jié)點上的連邊數(shù)。其中,s99與s100空間節(jié)點上連邊數(shù)最多,為115條,這兩個空間節(jié)點和幾乎所有的時間節(jié)點(共116個)都存在連邊。說明既存在沒有耦合事件發(fā)生的基站也存在幾乎一直發(fā)生耦合事件的基站。
耦合二分網(wǎng)絡中存在兩類節(jié)點(時間節(jié)點和空間節(jié)點),對應地,存在時間節(jié)點度和空間節(jié)點度。時間節(jié)點度指時間節(jié)點代表的某時期內有耦合事件發(fā)生的基站個數(shù)。時間節(jié)點度越大,表明此時期,空間上大范圍內發(fā)生了耦合事件,即吞吐量和話務量動態(tài)變化相似。空間節(jié)點度指某基站耦合事件發(fā)生的次數(shù)??臻g節(jié)點度越大,表明此基站上耦合事件大量發(fā)生,即吞吐量話務量動態(tài)變化高度相似。圖中綠色空間節(jié)點度大,說明其代表的基站上耦合事件多次發(fā)生。
將耦合二分網(wǎng)絡投影得到加權的時間單分網(wǎng)絡,可以研究耦合事件發(fā)生時間的規(guī)律。時間單分網(wǎng)絡是一個完全圖,網(wǎng)絡中節(jié)點度均為115,說明任意兩個時間段內至少一個基站上發(fā)生了耦合事件。邊權代表兩個時間段內均有耦合事件發(fā)生的基站個數(shù)。時間單分網(wǎng)絡的邊權分布為對數(shù)正態(tài)分布,如圖4a所示,擬合函數(shù)為p(w)=0.156 4e-3.771 8(lgw-1.717)2,擬合優(yōu)度[22]R2=0.920 4。強度為邊權之和[23],代表某時間段與其他全部時間段內發(fā)生耦合事件基站的總數(shù)。時間單分網(wǎng)絡的累積強度分布為線性分布,如圖4b所示,散點呈直線。擬合函數(shù)為P(s)=-0.001 0s+1.496 0,擬合優(yōu)度R2=0.981 3。
圖4 邊權分布和累積強度分布Fig.4 Edge weight distribution and cumulative strength distribution
耦合二分網(wǎng)絡中存在孤立節(jié)點42個,投影成空間單分網(wǎng)絡后,空間單分網(wǎng)絡中也存在孤立節(jié)點42個。我們分析空間單分網(wǎng)絡的最大連通子圖,稱空間單分網(wǎng)絡的最大連通子圖為S網(wǎng)絡(Spatial Network)。S網(wǎng)絡的集聚系數(shù)為0.836,平均路徑長度為1.42,S網(wǎng)絡屬于小世界網(wǎng)絡。
節(jié)點度為與節(jié)點直接相連的邊的數(shù)量,S網(wǎng)絡節(jié)點度k表示此節(jié)點對應的基站與k個基站在某時間段內吞吐量與話務量發(fā)生了耦合。S網(wǎng)絡的累積度分布為線性分布,如圖5a所示,擬合函數(shù)為P(k)=-0.010 6k+0.773 6,擬合優(yōu)度R2=0.983 3。強度為節(jié)點連邊權重的和,S網(wǎng)絡節(jié)點強度表示此節(jié)點對應的基站與其他所有基站有耦合事件發(fā)生的總數(shù)。S網(wǎng)絡的累積強度分布為指數(shù)分布,如圖5b所示,擬合函數(shù)為P(s)=0.606 4e-0.001 6s,擬合優(yōu)度R2=0.992 7。邊權為連邊的權重,S網(wǎng)絡中邊權w表示兩基站在w個時間段上都有耦合事件發(fā)生。S網(wǎng)絡的邊權分布為冪律分布,如圖5c所示,雙對數(shù)坐標下,散點呈直線。擬合函數(shù)為p(w)=0.149 8w-0.794 8,擬合優(yōu)度R2=0.911 6。表明S網(wǎng)絡的邊權具有無標度特性。
圖5 累積度分布、累積強度分布和邊權分布Fig.5 Cumulative degree distribution,cumulative strength distribution and edge weight distribution
基站可能會遭受突發(fā)攻擊,出現(xiàn)故障無法正常運行,進而影響整個系統(tǒng)的傳輸性能,本文對S網(wǎng)絡進行抗攻擊性分析。突發(fā)事件可能是隨機的,也可能是蓄意的,如遭受黑客攻擊等。依度對S網(wǎng)絡做蓄意攻擊,從去除網(wǎng)絡中度最大的節(jié)點開始,有意識地去除網(wǎng)絡中一部分度最高的節(jié)點。圖6a和圖6b分別反映了隨機和蓄意攻擊下S網(wǎng)絡最大連通子圖相對大小R和最短路徑長度L隨刪除節(jié)點比例f的變化情況。
圖6 抗攻擊性表現(xiàn)Fig.6 Robustness performance
在復雜的現(xiàn)象中發(fā)現(xiàn)有序時空規(guī)律是聚類分析的目的。為了識別網(wǎng)絡聚類特征,常用核心—邊緣結構模型來分析網(wǎng)絡[24-25]。核心—邊緣結構模型是使核心區(qū)與邊緣區(qū)的差異最大化[26-27]。核心—邊緣結構模型能識別出時間與空間聚集的區(qū)域。針對耦合二分網(wǎng)絡的最大連通子圖——C網(wǎng)絡做核心—邊緣模型結構分析,識別吞吐量與話務量耦合事件發(fā)生的時間和空間聚集區(qū)域。C網(wǎng)絡中時間節(jié)點116個,空間節(jié)點74個。得聚類后的密度矩陣為
表1 耦合比重劃分Tab.1 Division of coupling proportion
(8)
密度矩陣為兩行兩列,其中,第1行第1列的0.521為聚類后核心區(qū)的密度,第2行第2列的0.091為聚類后的邊緣區(qū)的密度。核心區(qū)與邊緣區(qū)的密度存在差異表示聚類后的核心區(qū)的兩類節(jié)點與邊緣區(qū)的兩類存在差異。聚類后得到核心空間節(jié)點(基站)30個、核心時間節(jié)點49個,邊緣空間節(jié)點44個、邊緣時間節(jié)點67個。核心—邊緣模型劃分出了耦合事件的發(fā)生時期與空間聚集區(qū)域。
為直觀表示核心區(qū)與邊緣區(qū)的差異,根據(jù)基站在特定時間段內吞吐量與話務量耦合事件發(fā)生的多少,定義耦合比重
(9)
其中,hi為基站耦合事件發(fā)生的頻數(shù),即耦合單元數(shù);n為核心區(qū)或者邊緣區(qū)時間節(jié)點的個數(shù)。fi取值為0到1,越接近于1表明基站上耦合事件發(fā)生的越多。確定如表l所示耦合比重劃分。
依據(jù)聚類結果,分別畫出在核心區(qū)與邊緣區(qū)時間節(jié)點代表的時間段內的基站在地理位置上的分布。如圖7a和圖7b所示。圖7a為核心區(qū)時間段內基站在地理位置上的分布;圖7b為邊緣區(qū)時間段內基站在地理位置上的分布。其中,節(jié)點顏色是根據(jù)對耦合比重的劃分確定的,弱耦合為藍色,中弱耦合為綠色,中強耦合為黃色,強耦合為紅色。
圖7 核心區(qū)與邊緣區(qū)的基站在地理上的離散分布Fig.7 The geographical discrete distribution of base stations in the core area and the periphery area
總體來看,圖7a中紅色和黃色節(jié)點多,圖7b中除3個節(jié)點為綠色外,其余節(jié)點均為藍色。表明核心時間段內的耦合比重高于邊緣時間段內的耦合比重,核心區(qū)耦合事件的發(fā)生頻率高于邊緣區(qū)耦合事件的發(fā)生頻率。無論是時間上還是空間上,核心—邊緣模型有效識別了不同時間段內的群聚群發(fā)區(qū)域。對于核心區(qū)域的節(jié)點,尤其是核心區(qū)紅色節(jié)點代表的基站值得重點關注,考慮新增基站或基站擴容以預防流量激增導致的網(wǎng)絡擁塞等問題。
基于吞吐量與話務量時空數(shù)據(jù),利用時間序列相似性度量與滑動時間窗口等數(shù)理統(tǒng)計方法,本文分析了某地區(qū)近6天的吞吐量與話務量數(shù)據(jù)時空變化特征。基于相似關系建立耦合二分網(wǎng)絡,將時空數(shù)據(jù)一體化。投影得到加權的時間單分網(wǎng)絡與空間單分網(wǎng)絡,分析單分網(wǎng)絡拓撲特征,展示耦合事件在時間和空間上的差異。對空間單分網(wǎng)絡做抗攻擊性分析,探討基站遭破壞后系統(tǒng)的穩(wěn)定性。利用核心邊緣模型分析吞吐量與話務量耦合的時空聚類特征。
耦合二分網(wǎng)絡中,空間節(jié)點間差異性比時間節(jié)點間差異性明顯,既存在沒有耦合事件發(fā)生的基站也存在幾乎一直發(fā)生耦合事件的基站。時間單分網(wǎng)絡為完全圖,邊權分布為對數(shù)正態(tài)分布。S網(wǎng)絡為小世界網(wǎng)絡,邊權分布為冪律分布。S網(wǎng)絡邊權具有無標度特性。此外S網(wǎng)絡的抗攻擊性強,網(wǎng)絡具有魯棒性。核心—邊緣模型時空聚類可以有效劃分核心空間節(jié)點和核心時間節(jié)點,核心區(qū)節(jié)點上吞吐量與話務量耦合事件發(fā)生頻率比邊緣區(qū)節(jié)點上的耦合事件發(fā)生頻率高。表明在核心區(qū)基站上,吞吐量與話務量動態(tài)變化十分相似。會出現(xiàn)基站吞吐量與話務量同時增大或同時減少的情況,值得進一步關注以預防流量激增導致的網(wǎng)絡擁塞等問題。
本文綜合了時間和空間維度信息以及時間與空間的相互關聯(lián)關系,構建時空耦合網(wǎng)絡。利用核心—邊緣模型對耦合二分網(wǎng)絡做聚類,聚類結果是既考慮時間又考慮空間的一個劃分。得到基站上吞吐量與話務量的群聚群發(fā)特征,為基站建設和管理提供了一些建議。本文的研究方法也為探索多事件耦合研究提供了新思路。