基于三角聚集度的社區發現標準在汽車消費人群分析的適用性研究

中國汽車技術研究中心 王文斌 白 辰 田 源

基于三角聚集度的社區發現標準在汽車消費人群分析的適用性研究

中國汽車技術研究中心 王文斌 白 辰 田 源

為解決汽車企業對于不同類型汽車消費人群的分析調研需求，本文研究了關系網絡中消費人群的社區發現問題，根據圖數據挖掘中三角型的特性，提出基于三角聚集度的社區發現標準。研究發現該方法對于車企的消費人群劃分判別具有很好的適用性。

汽車消費人群分析；社區發現；三角聚集度

1 引言

近年來，隨著網絡和各種電子設備的日益普及，越來越多人都參與到互聯網的信息交流中去。在眾多的網站中，Twitter、Facebook、微博、人人網、以及微信朋友圈等一系列社交網絡作為近年來廣泛使用的交流平臺，如雨后春筍般紛紛涌現出來，面向各個領域拓展自己的用戶。而那些現實生活中的人們因為各自的興趣愛好、地理位置、工作性質等原因所組成不同的“真實”群體，如何在這一“虛擬”的社交網絡中將其群體（或稱其為“社區”）標注提取出來，并挖掘這些群體的共同特點，發現知識、創造價值，已經成為社交網絡數據挖掘領域的一項研究熱點，“社區發現”作為一個新興的研究領域，也就因此成為研究者廣泛關注的問題。

2 社區發現

社交網絡反映了現實生活中的這樣一個特點：人們都會因為各自的興趣愛好，或所在地理位置、工作性質等原因而形成各種各樣的群體。而在社交網絡中，這些群體都會因為彼此的熟識或共同關注了某人或某物而有著較其他陌生人相比，更為頻繁的交流。那么利用這種關系，是否可以在社交平臺中復雜而龐大的用戶群體中找出這些現實的群體呢？因為若找出這些群體，必能通過這些群體的特征，利用數據挖掘的思想，找出類似“啤酒—尿布”的規律或知識，從而產生價值。

面對這個問題，學者們紛紛展開研究，“社交網絡挖掘”便成為數據挖掘領域一個新的重要分支，而社區發現是社交網絡挖掘的重點研究問題。例如在著名社交網站Facebook中截取的斯坦福大學學生之間的部分好友關系圖，就可以通過這種關系劃分出他們之間的關系：或同畢業于一個高中，或一同參加了一個暑期夏令營，或屬于不同的社團。

當然，社交網絡這一概念不僅僅指互聯網上的交友網站，它可以看作是由圖表示的異構關系數據集。現實世界中，在科技、商業、經濟和生物等方面，都有社交網絡的存在，比如汽車企業與客戶間的購買關系，汽車論壇中車友間信息的交流，以至萬維網、電力網格、計算機病毒傳播、電話交互圖以及科學家的合著關系、論文的引用網絡；生物學領域中的流行病學網絡，細胞與新陳代謝網絡和食物網絡等，都是社區發現的研究對象[4]。

但在這一社區發現這一新興領域進行算法的提出、對比和研究前，首先要確定一種合適的判別標準來確定這種劃分方法的好壞。現在使用最多的方法是2004年由M. Newman[1]提出的計算劃分社區的modularity （模塊性），但這一劃分標準的缺點也很明顯，它對于小型的社區并不適用。其他標準比如R. Kannan[2]提出的連通度（conductance），也存在對于一些聚集度極佳的特殊圖形，不能準確體現其聚集性質的缺點。

3 三角聚集度

3.1 圖數據中的三角形

圖中三角形的查找和統計在圖數據領域有著廣泛的研究意義和價值。因為三角形存在兩個重要特性——同質和傳遞，這兩個性質在社交網絡的圖數據挖掘中就起到了跟重要的作用：社交網絡的用戶傾向于與有用相似愛好和興趣的人建立朋友關系（在數據的角度，用戶之間擁有相似的三角形模式），這種傾向性在社交網絡中，主要表現在用戶更愿意與擁有相同朋友圈子的人成為朋友。同時，統計三角形也被應用于挖掘隱藏的網頁主題、彭谷聚類參數,以及檢測垃圾郵件。

3.2 聚集系數

其實最早在1949年R. D. Luce和A. D. Perry的一篇論文[3]中，圖中三角形的聚集度已經在圖論中被提出并定義這一系數為圖的聚集系數，描述的是圖中的若干點傾向于集聚在一起的程度的一種度量。

而圖中的某一個節點，聚集系數表示了它相連的點抱成團（完全子圖）的程度。為方便說明，這里定義在G = (V, E)中包含一系列節點V和連接它們的邊E。表示的第i個相鄰節點。表示的相鄰節點的數量。一個頂點的聚集系數等于所有與它相連的頂點之間所連的邊的數量，除以這些頂點之間可以連出的最大邊數。在無向圖中的最大邊數為，所以某一點的聚集系數公式表示為：

那么整個網絡的所有點聚集系數就可以定義為所有節點n的局部聚集系數的均值：

那么若一個圖的平均聚集系數比相同節點集生成的隨機圖有顯著提高，但平均最短距離卻與相應隨機生成的隨機圖十分相近，那么這個圖被認為是小世界的社交網絡圖。有著更高平均聚集系數的社交網絡被發現有著模塊結構，同時在不同節點中還有更小的平均距離。

3.3 三角聚集度

根據三角形在圖數據中的性質以及聚集系數這一指標，提出一種新的社區發現的度量標準——三角聚集度（Triangular-Clustering Coeffcient）

其公式定義如下：

在定義了節點對于社區的歸屬度的計算方法后，根據式（3.1）的思路，將這個社區內所有點的歸屬度取其平均值，得到計算這個社區C的整體的凝聚程度的表達式：

而后便可通過式（3.2）的思路確定該劃分對于整張圖來說劃分優劣的的一個指標即將各個社區根據其大小加權后平均即可：

3.4 度量標準分析

一個好的社區發現度量標準需要能很好的反映出根據此標準評判出的優秀社區的一些特點和屬性，這些屬性可以保證所劃分出的社區內節點的稠密性和結構特點。下面簡單對一個優秀社區的四個屬性進行簡單說明及分析：

屬性1：有良好的內部結構

在M. Newman等人之前的研究中已經表明，一個優秀社區的一個最主要的特征就是有一個數值非常大的聚集系數。社交網絡構成的圖數據與普通的隨機生成的圖的一個最大的不同也就是擁有非常多的三角形結構。因此，三角聚集度將計算三角形的個數作為計算一個社區聚集程度的一個最重要的評判標準。

屬性2：社區的凝聚力應隨節點增多而增長

在一個優秀的度量標準中，當一個新的節點被計算應當加入這個社區時，這個社區整體的凝聚程度應該是能夠得到增強的。放到實際情景中，若想加入一個社區，這個節點需要與這個社區內部很多的節點有聯系，這個社區越大，需要聯系的節點也就越多，它與這個社區的聯系才能體現出越強，越應該屬于這個社區，否則，這個社區整體的凝聚力將會因為它而降低。用函數形式表示，若節點x應屬于社區C，則。

屬性3：社區中不存在橋結構

在一個社區中若存在橋結構，則該社區的凝聚程度將會非常弱，因為除了這條邊之外，兩個節點集之間沒有任何的聯系。因此，一個優秀的社區中不應存在橋結構。

屬性4：社區中不存在割點

與橋結構類似，當在一個社區中存在若干個割點的話，若將此割點以及與之相連的邊刪除，則該社區立刻回分解成兩個互不關聯的子圖。所以割點也是一個社區中弱連接的體現，一個優秀的社區中，是不應該存在割點這一結構的。

可見，三角聚集度滿足以上的四種性質，同時用虛擬的小型社區數據計算其三角聚集度。如圖2所示，構建了從簡單稀疏的社區到復雜稠密的不同8個社區（從a到h），其三角聚集度的值由低至高，體現了這一度量標準能很好的體現社區的稠密程度。

4 總結

通過建立汽車消費人群的圖數據關系模型，研究了關系網絡中消費人群的社區發現問題以及圖數據挖掘中三角型的特性，并通過三角形的聚集系數的定義，提出基于三角聚集度的社區發現標準，并驗證了該標準對于車企的消費人群劃分判別的適用性。

本文中提出的標準對于大數據下的汽車社區網絡還沒有針對性其的成型算法實現，設計構思一種高效的使用三角聚集度計算的算法是今后的研究方向。

[1]M．Newman and M．Girvan．Finding and evaluating community structure in networks． Phy． Rev． E, 69(2):026113, 2004．

[2]R．Kannan et al．On clusterings:Good,bad and spectral．JACM, 51(3):497{515,2004．

[3]李曉佳,張鵬,狄增如等．復雜網絡中的社團結構[J]．復雜系統與復雜性科學,2008,5(3):19-42

[4]谷峪,于戈,鮑玉斌．大規模圖數據的分布式處理2015,ISBN-9787302420729．