基于時間序列相似性的網絡社區檢測方法

王鈞麟， 徐名海， 鄒敬博， 李小龍

（南京郵電大學通信與信息工程學院， 南京 210003）

0 引 言

現實世界中存在著許多復雜系統，在這些系統中實體之間的確切關系是未知的或者不易觀察到的，但仍然存在著非常明顯的社區結構。 例如，在萬維網中不同網站之間的關系是很難觀察到的，但根據每個網絡的主題不同可以發現萬維網中具有明顯的社區結構；在社會關系網絡中不同的人之間可能由于沒有交際導致其之間的關系不夠完整，但根據不同的行為習慣、消費習慣也呈現了明顯的社區結構；而在股票網絡中，某些股票之間的關系是無法得知的，但根據不同的行業或者價格漲跌等，股票網絡中也具有非常明顯的社區結構。 在復雜網絡中各個實體之間的確切關系是未知的、不完整的或不易觀察到的，本文將這樣的復雜網絡稱為隱邊網絡。

在隱邊網絡中，社區可以定義為具有相似的特定或者功能的個體的集合，在社區內部的每個個體之間的聯系較為緊密，而位于不同社區間的每個個體之間的聯系則較為稀疏。 認識和發現這些網絡中的社區結構具有非常高的實用價值，可以幫助了解系統的內在運行機制，還可以為這個系統進行預測和控制提供較強的指導和幫助。 為了了解復雜系統中實體之間的關系，可以觀察來自每個實體相互依賴的信號，如時間序列、事件序列等。 時間序列類型數據就是按照時間先后順序排列各個觀測記錄的數據集，在現實世界很多領域中都廣泛存在。

通過分析引起時間序列發生變化的具體內在原因，從而推斷出個體之間的關系，例如貝葉斯模型、非負張量分解等方法。 不同于觀察時間序列內在因素，本文選擇觀察每個個體時間序列的外在表現，通過分析每個個體之間時間序列的相似程度來表示其之間的關系，能夠更加簡單直觀地描述復雜系統中每個個體之間的關系。

1 相關關鍵技術

1.1 序列相似性度量

復雜系統中每個實體之間的關系通過其時間序列的外在表現，即時間序列之間的相似程度能夠更加簡單直觀地描述出來。 時間序列相似性度量有很多方法，如歐式距離、閔可夫斯基距離、皮爾遜相關系數、動態時間規整距離等。

歐式距離也稱為歐幾里得距離，是衡量時間序列之間距離最直接的方法，常常用來表示N維空間中兩個不同對象之間的相似性。 由于歐式距離的計算簡單高效，且可以體現時間序列中數值特征的絕對差異，因此常常用于時間序列相似性的度量。 但歐式距離只能計算相同長度的時間序列，不能實現數據異步匹配，且其度量質量容易受時間序列異常點、噪聲的影響，不能夠很好地滿足不同時間序列距離計算的需求。 閔可夫斯基距離則是一種更為廣泛的歐式距離，是歐式距離的推廣。

皮爾遜相關系數用于度量兩個變量X和Y之間的線性相關程度，兩個定距的連續隨機變量的皮爾遜相關系數等于兩者之間的協方差與各自標準差乘積的商，數值在-1 到1 之間。 系數值越接近于0，則隨機變量之間的相關程度就越低；系數值越接近于1，則變量之間呈現很強的相關關系。 系數的正負則表示了兩者之間呈現的正負相關關系。 皮爾遜相關系數的計算，式（1）：

其中，cov(X，Y) 為變量X和Y之間的協方差；σX，σY為變量X和變量Y的標準差；μX，μY為變量X和變量Y的均值。

動態時間規整距離是一種衡量兩個長度不同的時間序列之間相似度的方法，通過把時間序列延伸和縮短，使得不在同一時間點上對應的波峰或波谷也能夠被對齊，忽略不同時間序列之間在時間上的錯位與滯后的問題，具有較好的魯棒性。 本質上是通過最小化時間序列間的累計距離，以動態規劃的方式來尋找兩個時間序列之間最優的對齊路徑。 對于兩個長度不同的序列X＝(x1，x2，…，xm) 和Y＝(y1，y2，…，yn) ，序列之間點的距離定義為d(i，j) ，距離公式可以任意選定，可以簡單地選擇為歐氏距離；按照順序計算系列X中的每個點與序列Y中的每個點之間的距離，生成對齊矩陣。 為了獲得這個對齊矩陣，首先需要得到一個序列距離矩陣D，其中行對應X序列，列對應Y序列，矩陣元素D(i，j) 表示點xi與點yj之間的動態時間規整距離d(i，j) ，表示從原點 (0，0) 出發到達點(i，j) 需要累計的最小距離。D(i，j) 的計算，式（2）：

對齊矩陣中的D(m，n) 的值即為兩個序列之間動態時間規整距離的結果。

1.2 復雜網絡社區檢測

自2002 年Girvan 和Newman 基于邊介數提出GN（Girvan-Newman）算法進行社區檢測以來，國際上掀起了一股社團檢測的研究熱潮。 社區檢測早期的研究工作大部分都是圍繞非重疊社區檢測展開的，非重疊社區檢測算法識別出的社區之間互不重疊，每個節點僅屬于一個社區，包括基于圖分割的社區檢測算法和基于層次聚類的社區檢測算法等。

Kernighan-Lin 算法是典型的基于圖分割的社區檢測算法。 首先將網絡一分為二，形成兩個大小已知的集合，定義一個增益函數Q，表示集合中的內部邊連接數減去兩個集合之間的邊連接數，目標是通過改變節點間的連接使得增益函數最大化，最終獲得劃分結果。 該算法開始階段需要知道網絡的規模以及劃分個數，不適用于現實網絡。

基于層次聚類的社區檢測算法是通過衡量網絡中節點之間的相似度來檢測網絡中的社區，分為凝聚算法和分裂算法兩種。 凝聚算法的主要思想是將相似的節點不停地進行合并，直到合并為一個社區為止；而分裂算法則是將網絡中節點不斷進行劃分，直到每個節點代表一個社區。 GN 算法、Newman 快速算法和Louvain 算法等都是基于層次聚類的方法。 GN 算法屬于基于分裂的層次聚類算法，其主要思想：首先對網絡中每條邊的介數值進行計算，然后將介數值進行排序，每次選出其中的最大值，將該最大值所對應的連邊從網絡中移除，從而將網絡劃分為多個社區。 邊的介數值等于網絡的全部最短路徑中通過這條邊的路徑的個數與全部最短路徑個數的比值。 為了衡量網絡劃分的質量，又引入了模塊度函數的概念，當模塊度函數達到最大值時認為此時網絡劃分得最好。 而Louvain 算法是基于模塊度最優化的啟發式算法，該算法主要包含兩個階段，第一個階段不斷地遍歷網絡中的節點，嘗試將單個節點加入能使模塊度提升最大的社區中，直到所有節點都不再變化；第二個階段將第一階段形成的一個個小的社區歸并為一個超節點來重新構建網絡，并且計算其連邊權重。

2 現實應用場景和網絡社區檢測方法

2.1 現實應用場景

現實生活中存在著很多個體具有時間序列數據的復雜系統，利用這些時間序列數據進行網絡社區檢測的應用場景如圖1 所示。 圖1 中左半部分可以表示為復雜系統中的各個個體，各個個體之間的確切聯系是未知的、不完整的或者不易觀察到的，中間部分則是每個個體所對應的時間序列數據或事件序列數據，右半部分是根據中間部分的數據將左半部分的個體劃分為具有不同特征的社區結構。 例如，在一個道路交通系統中，左半部分的個體可以表示為每個不同的地點，根據每個地點地域是否相連等會存在一些聯系，但總體上聯系是不易觀察的，而每個地點具有交通客流量等時間序列的數據，可以表示為中間部分的數據；在一個社會關系系統中，左半部分的每個個體可以表示為不同的人，每個個體之間的確切關系可能不容易被觀察到，而中間部分則是每個人所對應的消費記錄、行為習慣或做某件事的頻率的一些時間或者事件序列的數據。 本文要在系統中個體之間的確切關系是未知或者不易觀察時，利用每個個體所對應的時間或者事件序列數據檢測出這些系統中具有不同特征的社區結構。

圖1 應用場景Fig. 1 Application scenario

2.2 基于時間序列相似性的網絡社區檢測方法

為了簡化復雜網絡的模型，本文假設在復雜系統中個體之間不存在任何關系和聯系，每個個體之間的聯系僅由其時間序列的相似性來決定。 首先，獲取到復雜系統中每個個體所對應的時間序列數據；其次，對每一對時間序列之間的相似性進行計算，得到每個個體之間的關系，從而可以構建出一個全連接的復雜網絡。

全連接的復雜網絡中包含了很多相似性較低的冗余信息，對整個系統和網絡的分析并沒有太大的價值。 因此，本文對網絡中節點之間的連邊進行篩選，去除網絡中一些不重要的邊，僅保留真正能反映節點之間關系的邊，使得對網絡的理解和分析更加準確，本文選擇閾值法來簡化網絡。 閾值法是通過確定一個特定的閾值，將距離小于選定閾值的連邊從網絡中過濾掉。 一般情況下，閾值的確定方式有兩種：一是通過觀察節點之間相似關系的分布給定相應的閾值；二是選取一個僅保留網絡中相似關系最高的前K%的連邊的閾值。 將相似性網絡簡化后，利用復雜網絡的社區檢測算法檢測復雜系統中的社區結構，并對其檢測結果進行理解和分析。

3 上證股票網絡社區實證分析

3.1 實驗數據獲取與預處理

上證180 指數成分股中的控股公司均是從金融、制造業、房地產等行業中挑選出的大型公司，這180 只股票的行業代表性較強、規模較大、流通性較好，能夠比較客觀且全面地描述上海股票市場的整體運行狀況和不同股票之間的關系。 因此，本文選取上證180 指數的所有成份股票作為研究對象，樣本數據為2020 年1 月1 日至2022 年3 月31 日每只股票在每個交易日的收盤價格，長期的時間跨度能夠保證樣本數據的有效性。

上證180 指數成分股票遵循穩定性與動態性相結合的原則，每隔一段時間就會對其中的股票進行一次調整。 為了確保實驗結果的有效性和可靠性，對于不能獲取這段時間內全部收盤數據的股票進行刪除，最終選取上證180 指數成分股中的162 只股票作為研究對象。

3.2 網絡構建與實驗結果分析

3.2.1 網絡的構建

為了更準確地描述股票價格的波動性，本文對獲取得到的股票收盤價時間序列進行歸一化處理，得到每只股票的對數收益率時間序列作為輸入，對數收益率的計算，式（3）：

其中，Pi(τ) 表示時間點τ的股票收盤價，Δt為計算對數收益率的時間間隔，通常取1 個交易日作為時間間隔。

得到每只股票對數收益率時間序列后，可以根據皮爾遜相關系數計算任意兩只股票i和j之間的相關系數，從而得到一個系數對稱矩陣C來描述這個全連接的股票網絡，系數矩陣C，式（4）：

其中，ρi，j表示股票i和股票j對數收益率序列的皮爾遜相關系數。

本文選用閾值法簡化全連接的股票網絡，需要對各個股票之間的相關系數進行統計分析，確定相應的閾值。 各股票間的對數收益率相關系數的概率分布曲線如圖2 所示，基本服從正態分布，只有很少數股票之間呈現負相關關系，絕大多數股票之間的相關系數都在0.2 ～0.4 之內，有極少數股票之間相關系數在0.8 以上。 這表明在股票市場中，絕大多數個股之間的相似關系并不顯著，僅有極少量的個股之間呈現出非常顯著的關聯關系。

圖2 股票間相關系數統計分布Fig. 2 Statistics of correlation coefficient between stocks

利用閾值法構建網絡，選取不同的閾值得到的網絡結構也是不同的。 若選擇的閾值較低，網絡中會保留較多次要的連邊，導致網絡過于復雜，難以提取其中的重要信息；反之，若選擇的閾值較高，雖然可以過濾掉絕大數冗余的信息，但此時網絡中連邊的數量過少，會使得一些有用的關聯信息丟失。 因此，本文一步一步提高閾值，得到一個穩定的網絡結構，從而確定一個合適的閾值。 選擇不同的閾值過濾后網絡中的有效連邊占初始網絡的比重如圖3 所示。

圖3 不同閾值時網絡中有效連邊所占比重Fig. 3 The proportion of effective edge connection in the network at different thresholds

觀察選取不同閾值過濾后得到的網絡，將閾值設定為0.4，經過過濾后的網絡連通圖如圖4 所示，此時的網絡被簡化，保留了重要連邊信息，同時網絡中也會出現一些孤立節點。

圖4 簡化后的股票網絡連通圖Fig. 4 Simplified connected graph of stock network

3.2.2 網絡結構特征分析

3.2.2.1 度和度分布

一個節點的度值越大，說明網絡中有越多的節點與這個節點之間存在直接的連邊，即該節點在網絡中的影響力越大。 在上證180 指數成分股票關聯網絡中，節點的度分布如圖5 所示。 為了更加直觀地判斷其度分布是否符合冪律分布，需要對累積度分布曲線進行擬合，得到股票關聯網絡的雙對數的累積度分布曲線如圖6 所示，該累計度分布曲線具有非常明顯的冪律特性，說明該股票關聯網絡具有無標度特性。

圖5 上證180 指數成分股票網絡節點度分布圖Fig. 5 Node degree distribution of Shanghai 180 index component stock network

圖6 上證180 指數成分股票網絡雙對數累積度分布圖Fig. 6 Distribution of double logarithmic cumulative degree of the stock network of the Shanghai 180 index components

3.2.2.2 平均路徑長度和聚類系數

將上證180 指數成分股票關聯網絡與模擬生成相同規模的隨機網絡的統計指標進行比較，結果見表1。 可以發現，上證180 指數成分股票關聯網絡具有小世界性。 因為該網絡的平均路徑長度較小，約等于隨機網絡的平均路徑長度，即在股票關聯網絡中的所有股票都能夠通過較短的路徑獲得關聯；并且該網絡的平均聚類系數遠大于隨機網絡的平均聚類系數，說明網絡中某只股票的價格發生變化時，其周圍的股票更容易受到影響，且受到影響的程度通常都比較大。

表1 上證180 指數成分股票網絡與隨機網絡統計指標Tab. 1 Shanghai 180 index component stock network and random network statistical indicators

3.2.3 網絡社區結構分析

本文運用Louvain 算法對上證180 指數成分股票關聯網絡進行社區劃分，整個股票網絡共被劃分為22 個社區，絕大部分股票被劃分在其中6 個社區中。 由于通過閾值法對連邊進行過濾時會產生一些孤立的節點，所以在社區劃分中通常都分別屬于不同的社區。 社區劃分后網絡中主要的社區中所包含的股票數量見表2，整個網絡社區劃分結果如圖7所示。

表2 上證180 指數成分股票網絡主要社區內部股票數量Tab. 2 Number of stocks within the main communities of the Shanghai 180 index stock network

圖7 上證180 指數成分股票網絡社區劃分結果圖Fig. 7 Result chart of Shanghai 180 index component stock network community division

從圖7 中可以看出，利用Louvain 算法對股票關聯網絡進行社區劃分的結果較好，社區的結構也較清晰。 為了進一步挖掘網絡中社區內股票的相關信息，本文統計了其中幾個主要的社區內部所有的股票信息，這些社區的股票構成見表3。 社區1 中的股票成員大部分都是能源以及基礎建設行業板塊的股票；在社區2 和社區3 中的股票成員分別屬于金融業中兩個不同的子行業，銀行和證券；在社區4 中都是一些來自制造業板塊的股票；而在社區5 中的股票成員則是屬于電子信息板塊。 通過社區劃分結構可見，大多數股票社區內部股票都呈現出具有同行業或者相關行業的特征，即隸屬于同一行業板塊的股票更加傾向于被劃分到同一個社區當中。 這也是符合常理的，因為屬于一個行業板塊的股票所面臨的市場環境和外部環境等因素都是類似的，受到經濟、供求關系以及政策的影響也是較為相同的，使得在同一個行業板塊的股票之間具有更加緊密的聯系，所以更傾向于劃分到同一個社區。 另外，本文還對每個社區中具有更高度值的節點進行分析，例如中國石化、浦發銀行、國泰君安屬于網絡中的關鍵節點，對整個社區乃至整個股票網絡的波動都會產生比較重大的影響。

表3 不同社區內的股票構成Tab. 3 Share composition in different communities

通過復雜網絡對股票網絡進行社區劃分是從定量的角度來衡量各個股票之間價格波動的相似性，比單純通過行業板塊進行區分更加精準。 在進行股票投資組合的時候，可以根據劃分的不同社區進行分散投資從而降低投資風險；而在不同社區進行投資時，則可以密切關注這些具有較高度值的股票，幫助投資者選取不同的股票進行投資。

4 結束語

本文基于時間序列的相似性以及復雜網絡理論對網絡中最重要的特性——社區結構進行了相應的分析，并利用上證180 指數成分股票的時間序列數據對其網絡進行了社區結構的分析，表明利用時間序列相似性對現實經驗世界中的復雜網絡的社區結構進行分析和解釋其內在運行機制是有效可行的。但本文忽略了復雜系統中每個個體之間原本存在著一定的聯系，僅僅利用每個個體時間序列之間的相似性表示每個個體之間的關系，沒有非常準確地描述現實場景。 未來的工作應該考慮保留復雜系統中個體之間原本的聯系，再結合時間序列之間的相似性，考慮復雜系統每個個體之間不同類型的關系的結合并分析其對復雜系統的社區結構的影響，從而能夠更精準地預測和控制這些復雜系統。