尹雅麗

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

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

尹雅麗

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

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

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

0 引言

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

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

1 社團(tuán)

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

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

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

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

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

2 Fast Unfolding算法

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

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

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

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

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

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

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

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

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

數(shù)據(jù)采集是本文研究的重點(diǎn)，同時(shí)也是數(shù)據(jù)分析的基礎(chǔ)。本文通過(guò)對(duì)人人網(wǎng)網(wǎng)站結(jié)構(gòu)分析，設(shè)計(jì)爬蟲，實(shí)現(xiàn)對(duì)人人網(wǎng)用戶ID的采集，然后根據(jù)ID采集每個(gè)用戶的信息。本文采集人人網(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)用戶個(gè)人資料、狀態(tài)采集模塊、和數(shù)據(jù)存儲(chǔ)模塊。

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

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

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

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

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

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

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

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

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

[8]姜志宏.大規(guī)模P2PTV系統(tǒng)測(cè)量與建模研究[D].博士,國(guó)防科學(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-），女，四川眉山人，研究生，研究方向?yàn)榫W(wǎng)絡(luò)安全、云計(jì)算

2016-03-01

2016－03－05

國(guó)家科技支撐計(jì)劃資助項(xiàng)目（No.2012BAH18B05）