尹雅麗

（四川大學(xué)計算機學(xué)院，成都 610065）

社交網(wǎng)絡(luò)數(shù)據(jù)采集方法研究及社團結(jié)構(gòu)分析

尹雅麗

（四川大學(xué)計算機學(xué)院，成都 610065）

在線社交網(wǎng)站擁有大量用戶，且越來越受歡迎。研究社交網(wǎng)絡(luò)的用戶行為和群體結(jié)構(gòu)特征對理解人類的社會行為、群體特征和加強對社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)理解具有重要意義。以人人網(wǎng)為例，詳細(xì)研究社交網(wǎng)站的數(shù)據(jù)采集技術(shù)，并對人人網(wǎng)社團結(jié)構(gòu)進行分析。研究發(fā)現(xiàn)：人人網(wǎng)具有明顯的社團結(jié)構(gòu)特征。研究成果對于進一步了解人人網(wǎng)等社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征具有重要意義，數(shù)據(jù)采集的結(jié)果為大數(shù)據(jù)分析奠定該基礎(chǔ)。

社交網(wǎng)絡(luò)；人人網(wǎng)；數(shù)據(jù)采集；社團

0 引言

隨著Web2.0時代的到來，互聯(lián)網(wǎng)技術(shù)蓬勃發(fā)展，各種社交網(wǎng)絡(luò)也在近幾年呈爆發(fā)式發(fā)展。人人網(wǎng)作為當(dāng)前比較流行的社交應(yīng)用之一，由中國互聯(lián)網(wǎng)絡(luò)信息中心（以下簡稱信息中心）2016年2月發(fā)布的調(diào)查結(jié)果來看[1]，人人網(wǎng)的使用率為15.6%，次于QQ空間（使用率為65.1%）和微博（33.5%）。雖然在近幾年人人網(wǎng)的用戶活躍度有所降低，但是它龐大的用戶群體仍然是值得深入研究的對象。人人網(wǎng)的用戶主體是大學(xué)生。據(jù)“信息中心”的調(diào)查結(jié)果，中國網(wǎng)民職業(yè)結(jié)構(gòu)中顯示，網(wǎng)民中學(xué)生群體的占比最高，為25.2%[1]，而學(xué)生群體是最容易受鼓動和利用的群里，容易被不法分子利用。因此對人人網(wǎng)發(fā)布信息的采集以及其合法性檢測對于輿情監(jiān)控和信息安全等都具有十分重要的意義。本文以人人網(wǎng)為例，分析其網(wǎng)站結(jié)構(gòu)特點，研究社交網(wǎng)站數(shù)據(jù)的采集技術(shù)，以網(wǎng)絡(luò)爬蟲為基礎(chǔ)，實現(xiàn)了人人網(wǎng)數(shù)據(jù)采集系統(tǒng)，并以采集到的真實數(shù)據(jù)為基礎(chǔ)，分析了人人網(wǎng)的社團結(jié)構(gòu)特點。

目前，國內(nèi)外針對社交網(wǎng)站的研究主要集中在社交網(wǎng)絡(luò)的拓?fù)浞治鯷2-3]、用戶行為特征分析[4-5]、社交網(wǎng)絡(luò)中的信息傳播[6]、安全隱私問題[7]、網(wǎng)絡(luò)拓?fù)溲莼Ｐ蚚8]等方面。尤婷[4]基于人人網(wǎng)用戶主頁的行為記錄數(shù)據(jù)，對個體行為和群體互動行為的時間統(tǒng)計特性進行實證研究；在對于人人網(wǎng)用戶行為的時間統(tǒng)計特性進行深度分析基礎(chǔ)上，針對人人網(wǎng)群體互動行為設(shè)計了社交驅(qū)動系數(shù)影響下的興趣驅(qū)動模型；利用MATLAB工具對該模型進行了有效的驗證，并根據(jù)實證分析驗證結(jié)論，給出社交網(wǎng)站產(chǎn)品改進及盈利模式探索的建議。鄧夏偉[5]分析社交網(wǎng)絡(luò)中的用戶行為，總結(jié)出了SNS中的用戶行為圖譜，探討了SNS中用戶行為數(shù)據(jù)的采集，并根據(jù)采集到的樣本對用戶行為進行數(shù)據(jù)分析，研究了社交網(wǎng)絡(luò)中的用戶影響力模型。

1 社團

社團（也稱為“社區(qū)”、“簇”、“模塊”）是一組內(nèi)部聯(lián)系緊密，外部聯(lián)系稀疏的節(jié)點集合[9]。圖1是一個小規(guī)模的包含三個社團的網(wǎng)絡(luò)結(jié)構(gòu)示意圖：

圖1 小規(guī)模社團示意圖

數(shù)學(xué)描述：設(shè)圖G=G（V，E），所謂社區(qū)發(fā)現(xiàn)是指在圖中確定nc（>=1）個社區(qū)：

使得各社區(qū)的頂點集合構(gòu)成V的一個覆蓋[10]。

社團這個概念最初由Girvan和Newman提出[11]，逐漸被廣泛引用，經(jīng)過十多年的發(fā)展，越來越成熟，現(xiàn)以成為復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域的熱點和重要研究方向。比較經(jīng)典的社區(qū)發(fā)現(xiàn)案例包括空手道俱樂部（Karate Club），科學(xué)家合作網(wǎng)絡(luò)（Collaboration Network）和斑馬群體(Zebras)的社交行為研究等，其中著名的空手道俱樂部社區(qū)已經(jīng)成為通常檢驗社區(qū)發(fā)現(xiàn)算法效果的標(biāo)準(zhǔn)（benchmark）之一。

2 Fast Unfolding算法

Fast Unfolding算法最初是由Vincent D.Blondel等人于2008年提出[12]，它是一種基于Modularity Opti-mization的啟發(fā)式算法，算法流程如下：

（1）初始化，將每個節(jié)點劃分在不同的社區(qū)中；

（2）逐一選擇各個節(jié)點，根據(jù)公式（1）計算將它分到它的鄰居社區(qū)中得到Modularity增益；如果最大增益大于0，則將它劃分到對應(yīng)的鄰居社區(qū)；否則，保持歸屬于原社區(qū)；

（3）重復(fù)（2），直到節(jié)點的社區(qū)不再發(fā)生變化；

（4）構(gòu)建新圖；新圖中的點代表上一階段產(chǎn)生的不同社區(qū)，邊的權(quán)重為兩個社區(qū)中所有節(jié)點對的邊權(quán)重之和；重復(fù)（2），直到獲得最大的Modularity值。

該算法的優(yōu)點：

●算法步驟直觀、實現(xiàn)簡單，且結(jié)果是無監(jiān)督的。

●該算法非?？欤河嬎銠C模擬大規(guī)模網(wǎng)絡(luò)，使用經(jīng)典的稀疏矩陣，其復(fù)雜度為：O(n)。原因是使用公式（2-1），在幾輪步驟后，社區(qū)數(shù)量大幅減小，大部分的運行時間集中在第一個迭代過程中。

3 人人網(wǎng)數(shù)據(jù)采集系統(tǒng)

數(shù)據(jù)采集是本文研究的重點，同時也是數(shù)據(jù)分析的基礎(chǔ)。本文通過對人人網(wǎng)網(wǎng)站結(jié)構(gòu)分析，設(shè)計爬蟲，實現(xiàn)對人人網(wǎng)用戶ID的采集，然后根據(jù)ID采集每個用戶的信息。本文采集人人網(wǎng)數(shù)據(jù)的系統(tǒng)架構(gòu)如圖2所示：

圖2 人人網(wǎng)數(shù)據(jù)采集系統(tǒng)框架

該系統(tǒng)由四部分組成，分別是人人網(wǎng)用戶ID和用戶好友關(guān)系采集模塊、人人網(wǎng)用戶個人資料、狀態(tài)采集模塊、和數(shù)據(jù)存儲模塊。

（1）人人網(wǎng)用戶ID和用戶好友關(guān)系采集模塊

該模塊主要用于采集用戶ID用戶個人信息和好友ID，本文通過調(diào)用人人網(wǎng)API，以廣度優(yōu)先的方式采集人人網(wǎng)用戶ID和人人網(wǎng)的好友關(guān)系。首先，在網(wǎng)絡(luò)爬蟲采集數(shù)據(jù)之前，需要實現(xiàn)人人網(wǎng)的模擬登錄過程。其次，通過Web網(wǎng)絡(luò)爬蟲的方式能夠采集到一些數(shù)據(jù)，但是大部分用戶設(shè)置了訪問權(quán)限，或者有些用戶已經(jīng)注銷了人人賬號，使得信息獲取不完整。本文采用調(diào)用人人網(wǎng)提供API獲取數(shù)據(jù)。

圖3展示獲取的部分好友關(guān)系構(gòu)成的拓?fù)浣Y(jié)構(gòu)圖：

圖3 人人網(wǎng)部分好友關(guān)系結(jié)構(gòu)圖

（2）人人網(wǎng)用戶個人資料和狀態(tài)采集模塊

該模塊根據(jù)上一步采集到的用戶ID組合特定的URL鏈接，通過HTTP協(xié)議請求指定用戶的個人資料頁面和狀態(tài)頁面，并通過正則表達(dá)式提取出用戶的個人資料和狀態(tài)。用戶狀態(tài)信息也是使用類似的方法獲取。

（3）數(shù)據(jù)存儲模塊

該模塊負(fù)責(zé)將上述四個模塊采集到的數(shù)據(jù)存儲到數(shù)據(jù)庫表中，用于各個模塊調(diào)用和后續(xù)數(shù)據(jù)分析。

4 社團結(jié)構(gòu)發(fā)現(xiàn)

本文使用上文中介紹的Fast Unfolding算法對人人網(wǎng)數(shù)據(jù)進行社團發(fā)現(xiàn)，選擇3組數(shù)據(jù)，結(jié)果如下：

表2 人人網(wǎng)社區(qū)劃分結(jié)果

由表2可以看出，隨著數(shù)據(jù)集的增大，人人網(wǎng)用戶關(guān)系網(wǎng)絡(luò)的社區(qū)劃分結(jié)果的模塊度值越來越高，這說明當(dāng)數(shù)據(jù)越來越接近真實水平時，模塊度的值也越來越接近真實水平。同時，人人網(wǎng)社區(qū)劃分結(jié)果具有較高的模塊度值，也和數(shù)據(jù)采集策略有關(guān)，本文數(shù)據(jù)采集時是從用戶ID出發(fā)，獲取其所有好友，在獲取好友的好友，以此類推。因此，結(jié)果表明，人人網(wǎng)用戶關(guān)系網(wǎng)絡(luò)具有較強的社區(qū)結(jié)構(gòu)特征。

5 結(jié)語

本文以人人網(wǎng)為例，研究社交網(wǎng)絡(luò)的數(shù)據(jù)采集技術(shù)，設(shè)計了人人網(wǎng)數(shù)據(jù)采集系統(tǒng)；并根據(jù)真實數(shù)據(jù)，對人人網(wǎng)進行社團發(fā)現(xiàn)。實驗結(jié)果表明，人人網(wǎng)是具有高度社團結(jié)構(gòu)的社交網(wǎng)絡(luò)，根據(jù)數(shù)據(jù)集大小的不同，模塊度的值有所變化，但是整體模塊度的值都在0.9以上。

[1]中國互聯(lián)網(wǎng)絡(luò)信息中心（CNNIC）.第37次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計報告[R].北京：中國互聯(lián)網(wǎng)信息中心,2016.

[2]陳興蜀,郝正鴻,王海舟,胡鑫.P2P網(wǎng)絡(luò)電視拓?fù)錅y量方法研究與特性分析[J].四川大學(xué)學(xué)報:工程科學(xué)版，2012,44(3):86-94.

[3]王勇,云曉春,李奕飛.對等網(wǎng)絡(luò)拓?fù)錅y量與特征分析[J].軟件學(xué)報,2008,19(4):981-992.

[4]尤婷.社交網(wǎng)站用戶行為特征及其內(nèi)在機制研究——以“人人網(wǎng)”為例[D].碩士,北京郵電大學(xué),2012.

[5]鄧夏偉.基于社交網(wǎng)絡(luò)的用戶行為研究——用戶行為分析與用戶影響力建模[D].碩士,2012,北京交通大學(xué).

[6]劉衍珩,李飛鵬,孫鑫,等.基于信息傳播的社交網(wǎng)絡(luò)拓?fù)淠Ｐ蚚J].通信學(xué)報,2013,34(4):1-9.

[7]孫劍,朱曉妍,劉沫盟,等.社交網(wǎng)絡(luò)中的安全隱私問題研究[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用,2011(10):76-79.

[8]姜志宏.大規(guī)模P2PTV系統(tǒng)測量與建模研究[D].博士,國防科學(xué)技術(shù)大學(xué),2011.

[9]Newman M E J,Girvan M.Finding and Evaluating Community Structure in Networks[J].Physical review E,2004,69(2):026113.

[10]Community Detection算法[EB/OL].http://blog.csdn.net/itplus/article/details/9286905.2016.2.25

[11]Girvan M,Newman M E J.Community Structure in Social and Biological Networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.

[12]Blondel V D,Guillaume J L,Lambiotte R,et al.Fast Unfolding of Communities in Large Networks[J].Journal of Statistical Mechanics: Theory and Experiment,2008(10):P10008.

Social Network Data Collection Method Research and the Community Structure Analysis

YIN Ya-li

(College of Computer Science,Sichuan University,Chengdu 610065)

Online social networking sites have a large number of users,and more and more popular.Research of social network user behavior and group structure features in understanding human social behavior,group characteristics,and strengthen the social network topological structure of understanding is of great significance.Takes Renren as an example,studies the data acquisition technology,social networking sites and analyzes the Renren community structure in details.The study found that:Renren have clear community structure.This research results for the further understanding of the Renren and other social networks topology structure is of great significance,the results of the data acquisition has paved the way for the big data analysis.

SNS;Renren;Data Collection;Community Structure

1007-1423（2016）08-0031-04

10.3969/j.issn.1007-1423.2016.08.006

尹雅麗（1989-），女，四川眉山人，研究生，研究方向為網(wǎng)絡(luò)安全、云計算

2016-03-01

2016－03－05

國家科技支撐計劃資助項目（No.2012BAH18B05）