基于社會(huì)網(wǎng)絡(luò)分析的權(quán)威網(wǎng)頁(yè)挖掘研究

張榮磊++宋洋++田愛奎++譚浩

摘要：該論文利用社會(huì)網(wǎng)絡(luò)分析法，對(duì)Web上特定主題的權(quán)威網(wǎng)頁(yè)進(jìn)行了挖掘。實(shí)驗(yàn)通過Google搜索引擎選取一定數(shù)量的待驗(yàn)證權(quán)威網(wǎng)頁(yè)，并利用網(wǎng)絡(luò)爬蟲爬取一定數(shù)量的URL，構(gòu)造了特定主題的網(wǎng)絡(luò)結(jié)構(gòu)，然后利用中心性分析以及凝聚子群分析挖掘出該特定網(wǎng)絡(luò)的權(quán)威網(wǎng)頁(yè)，通過與待驗(yàn)證權(quán)威網(wǎng)頁(yè)進(jìn)行比較，驗(yàn)證了實(shí)驗(yàn)方法的正確性，最后，對(duì)實(shí)驗(yàn)方法的后續(xù)改進(jìn)進(jìn)行了探討。

關(guān)鍵詞：社會(huì)網(wǎng)絡(luò)分析；權(quán)威網(wǎng)頁(yè)；URL；網(wǎng)絡(luò)爬蟲；中心性分析

中圖分類號(hào)： G350 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)：1009-3044（2016）20-0069-03

萬(wàn)維網(wǎng)的出現(xiàn)以及快速發(fā)展使得網(wǎng)絡(luò)上的網(wǎng)頁(yè)數(shù)量呈現(xiàn)爆炸式的增長(zhǎng)，截止2014年底，僅中國(guó)的網(wǎng)頁(yè)數(shù)量就已達(dá)到1899億個(gè)，年增長(zhǎng)26.6%[1]。如何快速、有效的從數(shù)以千億級(jí)的網(wǎng)頁(yè)中尋找到用戶需要的網(wǎng)頁(yè)信息，成為學(xué)術(shù)界廣泛關(guān)注的一個(gè)話題。互聯(lián)網(wǎng)中的網(wǎng)頁(yè)鏈接關(guān)系跟現(xiàn)實(shí)社會(huì)中人與人之間的關(guān)系相類似，而社會(huì)網(wǎng)絡(luò)分析方法又是分析人類群體關(guān)系的主要分析方法，如果將社會(huì)網(wǎng)絡(luò)分析法應(yīng)用于網(wǎng)頁(yè)信息搜索，是否會(huì)有同樣的效果？本文通過進(jìn)行實(shí)驗(yàn)分析，對(duì)社會(huì)網(wǎng)絡(luò)分析法應(yīng)用于權(quán)威網(wǎng)頁(yè)挖掘的可行性進(jìn)行了驗(yàn)證。

1基于主題的網(wǎng)頁(yè)關(guān)系構(gòu)建

由于Google搜索引擎是基于PageRank算法設(shè)計(jì)實(shí)現(xiàn)的，實(shí)驗(yàn)利用Google搜索引擎進(jìn)行權(quán)威網(wǎng)頁(yè)的選取。將獲取到的權(quán)威網(wǎng)頁(yè)作為種子URL，利用設(shè)計(jì)的網(wǎng)絡(luò)爬蟲對(duì)種子URL進(jìn)行給定深度的爬取，獲取實(shí)驗(yàn)需要的原始URL數(shù)據(jù)集。

1.1 種子URL選取

首先選取任意主題信息，如“Python”，并利用Google搜索引擎對(duì)“Python”進(jìn)行搜索，取排名前50位的網(wǎng)頁(yè)，記錄并保存網(wǎng)頁(yè)地址作為需要驗(yàn)證的權(quán)威網(wǎng)頁(yè)部分URL如表1所示。

1.2 利用網(wǎng)絡(luò)爬蟲獲取URL

利用設(shè)計(jì)的網(wǎng)絡(luò)爬蟲對(duì)50條種子URL分別進(jìn)行深度為1的爬取，總共得到約5500條子URL。這5500條原始URL包含大量重復(fù)及無(wú)效網(wǎng)頁(yè)，如廣告網(wǎng)頁(yè)、過期網(wǎng)頁(yè)，因此還需要對(duì)這部分URL進(jìn)行相應(yīng)的處理。

去重完畢后還需要對(duì)獲取到的URL集進(jìn)行有效性處理，將URL輸入瀏覽器，查看是否屬于廣告鏈接或者過期網(wǎng)頁(yè)。大部分無(wú)效URL對(duì)實(shí)驗(yàn)的結(jié)果不會(huì)產(chǎn)生影響，可以忽略無(wú)效URL的濾取，但忽略這一步會(huì)使后續(xù)分析更復(fù)雜，因此要盡可能過濾無(wú)效URL。最終種子URL與爬取到的URL共323條。

1.3 構(gòu)建URL鄰接矩陣

社會(huì)網(wǎng)絡(luò)分析需要的是矩陣形式的數(shù)據(jù)，因此，需要將獲取到的URL整理成鄰接矩陣形式。由于URL長(zhǎng)度過長(zhǎng)，數(shù)據(jù)錄入不方便，因此實(shí)驗(yàn)中將每一條URL用數(shù)字編號(hào)代替，如表2所示。

利用Excel 2007或后續(xù)版本進(jìn)行鄰接矩陣的輸入，將編號(hào)1至323分別輸入到第一行與第一列。矩陣中的任一項(xiàng)aij代表第i條URL與第j條URL之間的鏈接關(guān)系，為1表示編號(hào)為i的URL鏈接了編號(hào)為j的URL，反之則代表沒有鏈接關(guān)系。在對(duì)矩陣進(jìn)行0、1分析時(shí)，由于涉及子ULR的鏈接，因此還需要對(duì)子URL進(jìn)行深度為1的爬取，以確認(rèn)子URL與其他URL之間的鏈接關(guān)系。對(duì)角線上的值由于沒有意義不進(jìn)行處理，最終得到一個(gè)323×323的鄰接非對(duì)稱矩陣，后續(xù)在進(jìn)行社會(huì)網(wǎng)絡(luò)分析時(shí)還需要對(duì)該非對(duì)稱矩陣其進(jìn)行對(duì)稱化處理。

2 實(shí)驗(yàn)分析

社會(huì)網(wǎng)絡(luò)分析通常利用中心性分析以及凝聚子群分析等多種方法對(duì)人類社會(huì)群體進(jìn)行分析。通過中心性分析可以了解到一個(gè)群體中每個(gè)成員的重要程度，比較常用的中心性指標(biāo)有：點(diǎn)度中心度與點(diǎn)度中心勢(shì)、中間中心度與中間中心勢(shì)和接近中心度與接近中心勢(shì)。利用中心性分析可以對(duì)URL鏈接進(jìn)行相同的分析，從而明確URL網(wǎng)絡(luò)結(jié)構(gòu)圖中每條URL的重要程度，越重要的URL則可以認(rèn)為它具有更高的權(quán)威性。

2.1 中心性分析

1） 點(diǎn)度中心度分析

點(diǎn)度中心度分析就是對(duì)網(wǎng)絡(luò)結(jié)構(gòu)圖中的成員節(jié)點(diǎn)進(jìn)行出入度計(jì)算。點(diǎn)入度即指向某一節(jié)點(diǎn)的節(jié)點(diǎn)成員數(shù)，點(diǎn)出度則為該節(jié)點(diǎn)指向其他節(jié)點(diǎn)的成員數(shù)。一個(gè)節(jié)點(diǎn)若被網(wǎng)絡(luò)中的大多數(shù)節(jié)點(diǎn)所指向，那么就可以認(rèn)為它在網(wǎng)絡(luò)中處于重要的位置，具有較高的權(quán)威性。

在UCINET[中選擇Network→centrality→Degree...，導(dǎo)入生成的.##h文件，UCINET會(huì)自動(dòng)生成并彈出.txt格式的中心性計(jì)算結(jié)果。計(jì)算結(jié)果包含網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的點(diǎn)入度與點(diǎn)出度，并且是以每個(gè)節(jié)點(diǎn)的點(diǎn)出度大小進(jìn)行的排名，而實(shí)驗(yàn)更加關(guān)注的是點(diǎn)入度，因此，需要按照每個(gè)URL的點(diǎn)入度大小從新進(jìn)行排序。部分排序結(jié)果如表3所示。

通過對(duì)點(diǎn)入度排名進(jìn)行分析發(fā)現(xiàn)，編號(hào)為46、95、128、148、150、186、241、242等URL具有較大的點(diǎn)入度值，且它們都屬于原50條種子URL，可以初步斷定這些URL具有一定的權(quán)威性。

2） 中間中心度分析

中間中心度用于分析群體成員作為媒介的能力。如果群體中某一個(gè)成員具有較高的中間中心度，那么他就可以通過控制與其他成員之間的信息交流來對(duì)整個(gè)群體產(chǎn)生影響。因此，可以認(rèn)為具有較高中間中心度的成員也具有一定的權(quán)威性。通過對(duì)URL網(wǎng)絡(luò)結(jié)構(gòu)圖進(jìn)行分析，那些具有較高中間中心度的URL就可以認(rèn)為它們比其他URL具有更高的權(quán)威性。

在分析中間中心度時(shí)，還需要對(duì)URL鄰接矩陣進(jìn)行對(duì)稱化處理，通過Transform→Symmetrize...，導(dǎo)入原.##h文件，自動(dòng)生成對(duì)稱化處理的Sym.##h文件。接著利用Network→Centrality→Freeman Betweenness→Node Betweenness，導(dǎo)入生成的Sym.##h文件，UCINET同樣彈出.txt格式的中間中心度計(jì)算結(jié)果，部分結(jié)果如表4所示。

觀察發(fā)現(xiàn)，中間中心度值較高的URL，如46號(hào)、95號(hào)、150號(hào)、186號(hào)、241號(hào)等，與前面點(diǎn)度中心度值較高的URL相吻合，即都屬于50個(gè)種子URL。

2.2 凝聚子群分析

中心性分析初步證明了社會(huì)網(wǎng)絡(luò)分析法在權(quán)威網(wǎng)頁(yè)挖掘的可行性，若利用凝聚分析同樣可以得到相同的結(jié)果，那么就可以認(rèn)為社會(huì)網(wǎng)絡(luò)分析法在權(quán)威網(wǎng)頁(yè)挖挖掘的正確性。凝聚子群分析也有多種分析方法，如：成分分析，n-派系和n-宗派分析，k-叢分析等。此實(shí)驗(yàn)只選取建立在點(diǎn)度基礎(chǔ)上的k-叢分析進(jìn)行驗(yàn)證。

在UCINET中選擇Network→Subgroups→K-Plex...，導(dǎo)入Sym.##h文件，設(shè)置相應(yīng)的k值、n值即可。k值、n值需要用戶自己多次嘗試才能最終得到合適的子群。經(jīng)過多次帶入k值、n值，最終k取2，n取5，得到46個(gè)子群，部分分析結(jié)果如表5所示。

觀察完整的表5叢分析結(jié)果，編號(hào)為46、49、150、164、241等URL在絕大多數(shù)子群中出現(xiàn)，說明它們?cè)诰W(wǎng)絡(luò)中具有重要作用，而這些URL同樣出現(xiàn)在中心性分析結(jié)果中，即都屬于50個(gè)種子URL。

至此可得出結(jié)論，利用社會(huì)網(wǎng)絡(luò)分析得到的網(wǎng)頁(yè)符合權(quán)威網(wǎng)頁(yè)的特征，該方法正確性得以驗(yàn)證。

3 結(jié)語(yǔ)

實(shí)驗(yàn)首先利用較為成熟的Google搜索引擎搜索給定主題的URL，并利用網(wǎng)絡(luò)爬蟲爬取一定數(shù)量的URL集，隨后利用社會(huì)網(wǎng)絡(luò)分析法對(duì)收集到的URL集進(jìn)行了分析，最后得出：利用中心性分析以及凝聚子群分析得到的網(wǎng)頁(yè)符合權(quán)威網(wǎng)頁(yè)的特征，從而證實(shí)了實(shí)驗(yàn)的有效性。

但該實(shí)驗(yàn)方法也存在一定的不足：

1） 實(shí)驗(yàn)數(shù)據(jù)的整理工作需要手動(dòng)進(jìn)行，需要耗費(fèi)大量精力。后續(xù)研究需要找到快速處理URL的方法。

2） 實(shí)驗(yàn)用到的網(wǎng)絡(luò)爬蟲功能較為簡(jiǎn)單，在使用網(wǎng)絡(luò)爬蟲時(shí)會(huì)爬取到大量與給定主題無(wú)關(guān)的網(wǎng)頁(yè)，這也是造成數(shù)據(jù)整理困難的主要原因。后續(xù)工作將增加網(wǎng)絡(luò)爬蟲的功能，使其能夠爬取給定主題的網(wǎng)頁(yè)。

3） URL爬取量也較少，導(dǎo)致URL網(wǎng)絡(luò)結(jié)構(gòu)稀疏，影響實(shí)驗(yàn)的可信度。下一步在改進(jìn)網(wǎng)絡(luò)爬蟲功能的同時(shí)，還需要增加網(wǎng)絡(luò)爬蟲爬取的深度，使實(shí)驗(yàn)可信度更高。

參考文獻(xiàn)：

[1] 中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[R].中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心，2013.

[2] 王芳.基于主題的Deep Web搜索引擎研究與探索[D]. 長(zhǎng)安大學(xué)，2008.

[3] Kleinberg， J. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM， 1999，46（5）：604-632.

[4] Brin S， P. Lawrence. The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks， 1998， 30（1-7）：107-117.