語(yǔ)義社交網(wǎng)絡(luò)中用戶信息提取與影響力分析

邱 望，潘善亮

(寧波大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)研究所，浙江 寧波 315211)

1 引 言

21世紀(jì)是一個(gè)信息爆炸增長(zhǎng)的時(shí)代，人們能夠從外在的世界接收到豐富的信息，同時(shí)也渴望讓更多人接收到自己的信息.隨著互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展和移動(dòng)端硬件與通信技術(shù)的快速升級(jí)，人們可以非常快速和方便的獲取與傳遞各種信息.社交網(wǎng)絡(luò)由于其內(nèi)容豐富、時(shí)效性強(qiáng)、影響范圍大以及交互性強(qiáng)等特點(diǎn)，在人們發(fā)布信息、溝通交流和工作生活等方面扮演著不可替代的角色.社交網(wǎng)絡(luò)主要是通過(guò)實(shí)時(shí)熱點(diǎn)、興趣點(diǎn)和名人等媒介將用戶聯(lián)系起來(lái)，讓用戶愿意參與到其中從而保持活力，因此有影響力的人或事物在社交網(wǎng)絡(luò)中具有非常重要的作用.

社交網(wǎng)絡(luò)的海量數(shù)據(jù)和其巨大的關(guān)系網(wǎng)絡(luò)提供了非常大的價(jià)值，但同時(shí)也使得社交網(wǎng)站系統(tǒng)需要負(fù)擔(dān)越來(lái)越大的數(shù)據(jù)處理工作，因此需要一種更好的網(wǎng)絡(luò)關(guān)系結(jié)構(gòu)來(lái)提高系統(tǒng)的效率.語(yǔ)義網(wǎng)(Semantic Web)技術(shù)[1]為這個(gè)問題提供了一種可能的解決方案，它的思想是為每個(gè)事物添加一個(gè)或多專屬文檔，在文檔中使用結(jié)構(gòu)化的RDF(Resource Description Framework)[2]數(shù)據(jù)定義該事物與其它事物的語(yǔ)義關(guān)系，計(jì)算機(jī)可以根據(jù)給定的推理規(guī)則自動(dòng)推算出事物之間的關(guān)系.其中，F(xiàn)OAF(Friend of a friend)[3]是語(yǔ)義網(wǎng)中最受關(guān)注的項(xiàng)目之一，它被用于構(gòu)建基于語(yǔ)義社交網(wǎng)絡(luò)(Semantic Social Network).FOAF簡(jiǎn)檔(FOAF profiles)中的信息是由用戶自己添加維護(hù)，其中的信息具有穩(wěn)定可靠性，所以將語(yǔ)義網(wǎng)技術(shù)用于社交網(wǎng)絡(luò)可以建立一個(gè)信任度較高的關(guān)系網(wǎng)絡(luò).要研究社交網(wǎng)絡(luò)，首先需要一種能夠高效準(zhǔn)確提取信息的方法.由于RDF數(shù)據(jù)標(biāo)簽化的特點(diǎn)和FOAF簡(jiǎn)檔的隱性關(guān)系模式，提取用戶信息的關(guān)鍵就在于尋找相關(guān)聯(lián)的站點(diǎn)，從站點(diǎn)中獲取FOAF文檔并解析出有效的信息.另一方面，尋找有影響力的用戶也是非常重要.為了計(jì)算用戶的影響力，需要根據(jù)FOAF簡(jiǎn)檔中不同的語(yǔ)義信息得到個(gè)體之間的不同關(guān)系，據(jù)此量化用戶站點(diǎn)的重要性.

本文通過(guò)分析語(yǔ)義社交網(wǎng)絡(luò)中各實(shí)體與資源之間的鏈接情況得到實(shí)體鏈接模型，定義了一種FOAF簡(jiǎn)檔的通用特征模式，以此為基礎(chǔ)提出一種識(shí)別和發(fā)現(xiàn)有效FOAF簡(jiǎn)檔的方法；使用RDF解析器提取出FOAF簡(jiǎn)檔中的三元組信息并根據(jù)語(yǔ)義關(guān)系轉(zhuǎn)儲(chǔ)為關(guān)系型數(shù)據(jù)，對(duì)重復(fù)和冗余的數(shù)據(jù)進(jìn)行融合處理；根據(jù)實(shí)體的直接或間接的依賴關(guān)系計(jì)算依賴度權(quán)值，根據(jù)語(yǔ)義關(guān)系計(jì)算語(yǔ)義權(quán)值，據(jù)此計(jì)算出用戶站點(diǎn)的影響力大小并對(duì)其進(jìn)行排序，最終得到社交網(wǎng)絡(luò)中各用戶站點(diǎn)影響力的情況.

2 相關(guān)工作

隨著語(yǔ)義網(wǎng)技術(shù)研究的深入，語(yǔ)義社交網(wǎng)絡(luò)也受到了研究人員的關(guān)注，研究的內(nèi)容多種多樣，其中包括語(yǔ)義爬蟲、RDF數(shù)據(jù)分析、社交內(nèi)容的潛在信息、社會(huì)影響力和語(yǔ)義本體模型分析等.不同的文獻(xiàn)也從不同的研究角度提出解決的辦法.

許多文獻(xiàn)在提取用戶信息時(shí)是通過(guò)使用頁(yè)面中的超鏈接，采用類似傳統(tǒng)的HTML頁(yè)面爬蟲來(lái)抓取站點(diǎn)中的FOAF簡(jiǎn)檔，這種方法會(huì)遺漏大量相關(guān)的FOAF資源.文獻(xiàn)[4]對(duì)語(yǔ)義社交網(wǎng)絡(luò)的鏈接結(jié)構(gòu)進(jìn)行了研究分析，使用FOAF本體語(yǔ)義和語(yǔ)義Web推理技術(shù)對(duì)在線社交網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行了分析.但該方法并未對(duì)RDF數(shù)據(jù)進(jìn)行分析處理，并且未對(duì)網(wǎng)絡(luò)中的實(shí)體鏈接模型進(jìn)行分析，使得FOAF中相關(guān)聯(lián)的站點(diǎn)資源沒有被搜索到，最終得到的用戶關(guān)系網(wǎng)絡(luò)較稀疏和散亂.在RDF數(shù)據(jù)解析方面，由于FOAF屬性支持自定義，因此解析的數(shù)據(jù)會(huì)有很多的不常用屬性.Petrovic G在文獻(xiàn)[5]中提出的SoNeR模型提供了一種爬取RDF數(shù)據(jù)的方法并對(duì)數(shù)據(jù)進(jìn)行排序，同時(shí)使用Levenshtein距離來(lái)判斷字符串的相似度，但是該方法爬取到的數(shù)據(jù)中包含了很多不相關(guān)的FOAF簡(jiǎn)檔，同時(shí)計(jì)算字符串相似度的方法能夠優(yōu)化.

在計(jì)算影響力方面，已有的研究工作大都是面向傳統(tǒng)結(jié)構(gòu)的社交網(wǎng)絡(luò)，文獻(xiàn)[6]對(duì)已有的一些工作進(jìn)行了總結(jié)，從網(wǎng)絡(luò)拓?fù)洹⒂脩粜袨楹徒换バ畔⒌榷鄠€(gè)方面總結(jié)了影響力分析的建模和度量方法，由于影響因素非常多，這些方法的準(zhǔn)確度很高，但同時(shí)也有很高的復(fù)雜度.在語(yǔ)義結(jié)構(gòu)化的社交網(wǎng)絡(luò)中可以使用更高效的方法.在已有的語(yǔ)義社交網(wǎng)絡(luò)影響力的相關(guān)研究中，很多文獻(xiàn)都是側(cè)重于語(yǔ)義關(guān)聯(lián)，而沒有充分考慮到不同的語(yǔ)義屬性應(yīng)該有不同的權(quán)值.文獻(xiàn)[7]提出了一種自發(fā)的RDF收集系統(tǒng)Falcons，從Swoogle上發(fā)現(xiàn)了271 178個(gè)站點(diǎn)并進(jìn)行了排序，但該系統(tǒng)并未考慮站點(diǎn)之間語(yǔ)義屬性的影響因素，在重要度的計(jì)算和排序上可以進(jìn)一步優(yōu)化.Jennifer等在文獻(xiàn)[8]中使用了FOAF來(lái)計(jì)算社交網(wǎng)絡(luò)中用戶之間的信任度關(guān)系，該模型能夠得到間接關(guān)聯(lián)用戶之間的關(guān)系，該方法計(jì)算信任度時(shí)取0和1來(lái)代表不信任和信任，但在實(shí)際中信任度應(yīng)該是一個(gè)0到1之間的值，需要根據(jù)語(yǔ)義屬性量化出用戶影響力大小.TwitterRank[9]從用戶和鏈接結(jié)構(gòu)之間主題相似性的影響入手，以此來(lái)識(shí)別社交網(wǎng)絡(luò)中有影響力的用戶，這種方法為計(jì)算語(yǔ)義社交網(wǎng)絡(luò)用戶的影響力提供了思路.

現(xiàn)在的問題在于大多數(shù)信任度的計(jì)算方法都是基于傳統(tǒng)的超鏈接方式，很多都不適用于語(yǔ)義社交網(wǎng)絡(luò)中.這些方法從社交網(wǎng)絡(luò)中提取的RDF數(shù)據(jù)有效率較低，往往會(huì)得到大量的與用戶信息無(wú)關(guān)的FOAF簡(jiǎn)檔；由于RDF/XML格式的特點(diǎn)，直接從FOAF簡(jiǎn)檔中讀取數(shù)據(jù)并進(jìn)行計(jì)算需要花費(fèi)大量的時(shí)間且效率低下；在最后計(jì)算影響力的時(shí)候應(yīng)該考慮不同語(yǔ)義屬性的強(qiáng)弱程度.因此，針對(duì)以上得問題，本文提出一種完整的方法，能夠高效的提取用戶信息并進(jìn)行過(guò)濾，同時(shí)根據(jù)語(yǔ)義信息和關(guān)聯(lián)情況計(jì)算用戶的影響力.

3 用戶站點(diǎn)的發(fā)現(xiàn)與信息提取

3.1 語(yǔ)義社交網(wǎng)絡(luò)的鏈接模型

傳統(tǒng)的社交網(wǎng)絡(luò)系統(tǒng)中數(shù)據(jù)與實(shí)體之間不存在邏輯關(guān)系，因此從中找到實(shí)體之間的關(guān)系難度較大.研究者們通過(guò)超鏈接找到其他的HTML網(wǎng)頁(yè)[10]，采用信息抽取的方法，找到用戶的歷史資料和交互信息來(lái)分析用戶的特征和傾向.但由于人行為的不確定性和其他各種客觀因素，這一過(guò)程產(chǎn)生的結(jié)果往往不夠精準(zhǔn)和全面.

在語(yǔ)義社交網(wǎng)絡(luò)中，描述用戶關(guān)系的數(shù)據(jù)都存儲(chǔ)在FOAF簡(jiǎn)檔中，以實(shí)體為中心，通過(guò)各種語(yǔ)義屬性與其他實(shí)體進(jìn)行關(guān)聯(lián).語(yǔ)義社交網(wǎng)絡(luò)中各種實(shí)體的鏈接模式與傳統(tǒng)的模式不同，因此需要定義其鏈接模型，以此為基礎(chǔ)來(lái)發(fā)現(xiàn)用戶站點(diǎn)和數(shù)據(jù).定義如下的概念：

SWS(Semantic web sites)：語(yǔ)義網(wǎng)站點(diǎn)，它提供了語(yǔ)義網(wǎng)信息和資源.

Model：模型，語(yǔ)義網(wǎng)信息所表現(xiàn)出來(lái)的RDF模型，一般是一個(gè)FOAF簡(jiǎn)檔，由RDF語(yǔ)句來(lái)描述站點(diǎn)的信息及關(guān)系圖.

Entity：實(shí)體.FOAF簡(jiǎn)檔中定義了一組對(duì)象、概念以及這些對(duì)象、概念之間關(guān)聯(lián)的描述，這些對(duì)象和概念的集合就是一個(gè)Entity.

SWR(Semantic web resource)：語(yǔ)義網(wǎng)資源，即與Entity相關(guān)聯(lián)的對(duì)象.每個(gè)SWR都有一個(gè)URI(Uniform Resource Identifier，統(tǒng)一資源標(biāo)識(shí)符)，這個(gè)URI可以是鏈接，也可以是地理位置，電話號(hào)碼或字符串等.通過(guò)SWR的URI可以找到這個(gè)站點(diǎn)與其他站點(diǎn)或?qū)嶓w之間的聯(lián)系.

根據(jù)以上的概念，用戶站點(diǎn)是一個(gè)SWS，這個(gè)SWS提供了描述用戶信息的Model，以FOAF簡(jiǎn)檔的形式來(lái)表示.FOAF簡(jiǎn)檔中包含一個(gè)或多個(gè)Entity，其中描述了該用戶與其他用戶或?qū)嶓w的具體關(guān)系.Entity中的FOAF屬性表明了與其相關(guān)的URI，當(dāng)這個(gè)URI也是一個(gè)SWS時(shí)，即表示這兩個(gè)站點(diǎn)相關(guān)，這樣站點(diǎn)之間就有了類似于傳統(tǒng)HTML網(wǎng)頁(yè)中超鏈接的連接關(guān)系.定義其鏈接模型如圖1所示.

圖1 語(yǔ)義社交網(wǎng)絡(luò)鏈接模型Fig.1 Semantic social network linking model

根據(jù)該模型可以獲取到大部分相關(guān)聯(lián)的用戶數(shù)據(jù)，但由于SWR不一定指向SWS，也可能指向不包含RDF數(shù)據(jù)的其他實(shí)體，如果用戶A和用戶B同時(shí)指向一個(gè)非SWS對(duì)象，則表明他們?cè)趯?shí)際生活中可能存在間接關(guān)系.另外，在獲取到的FOAF簡(jiǎn)檔可能會(huì)存在很多無(wú)關(guān)的文檔，例如某些項(xiàng)目和公司的文檔，同樣需要對(duì)數(shù)據(jù)進(jìn)行處理和篩選.因此，我們?cè)诖嘶A(chǔ)之上，提出一種更有效和準(zhǔn)確的識(shí)別和發(fā)現(xiàn)在線FOAF簡(jiǎn)檔的方法，并將這種方法加入到FOAF簡(jiǎn)檔的解析中.

3.2 FOAF簡(jiǎn)檔的特征模式

我們可以很容易的測(cè)試出RDF文檔是否使用了FOAF命名空間，但是仍然需要提供明確的標(biāo)準(zhǔn)來(lái)確定文檔是否是FOAF簡(jiǎn)檔.由于FOAF簡(jiǎn)檔可能由具有各種意圖的不同作者發(fā)布，所以它并沒有固定的結(jié)構(gòu).雖然FOAF詞匯可以用于描述各種信息，但我們只關(guān)注包含個(gè)人信息的部分.為了給出FOAF簡(jiǎn)檔的正式定義，我們分析了本體語(yǔ)義和FOAF詞匯在使用的過(guò)程中所隱含的特征模式.使用以下3個(gè)特征模式定義嚴(yán)格的FOAF簡(jiǎn)檔D：

1)D是有效的RDF文檔，可以由RDF解析器驗(yàn)證它是否有效.

2)D使用FOAF命名空間.

3)D包含如圖2所示的RDF圖模式.在該圖中，A和B是兩個(gè)不同的rdfs：Resource實(shí)例，而C是一個(gè)使用FOAF命名空間的rdf：Property的實(shí)例.

圖2 FOAF簡(jiǎn)檔的特征模式Fig.2 FOAF profiles feature pattern

以上的特征模式可以排除掉絕大部分不含個(gè)人信息的文檔，因此，可以將其定義為FOAF簡(jiǎn)檔的通用模式.由于RDF/ XML通常用于編碼RDF，所以在本研究中我們只考慮以RDF/ XML編碼的RDF文檔.

根據(jù)上述模式，我們可以實(shí)現(xiàn)相應(yīng)的FOAF爬蟲和RDF數(shù)據(jù)解析器.FOAF簡(jiǎn)檔發(fā)現(xiàn)是一個(gè)迭代過(guò)程，由兩個(gè)步驟組成：

(i)使用網(wǎng)絡(luò)搜索引擎發(fā)現(xiàn)FOAF簡(jiǎn)檔潛在的鏈接；

(ii)運(yùn)行爬蟲發(fā)現(xiàn)新鏈接并進(jìn)行詞匯語(yǔ)義驗(yàn)證.

由于web搜索引擎將web文檔視為自由文本，我們將以上的3個(gè)特征模式轉(zhuǎn)換為有效查詢.根據(jù)第1種模式，我們只需要查詢足夠明確的使用了RDF模式的文檔[11]，即帶有.rdf，.xrdf，.owl等后綴的文檔.雖然這些后綴并不完全，但卻能夠找到大量的有效的RDF文檔.根據(jù)第2和第3種特征模式，我們使用了搜索的關(guān)鍵字的方法，即在第1種模式得到的文檔中查找滿足第2特征和第3特征的關(guān)鍵字，這些關(guān)鍵字包括FOAF命名空間，foaf：knows等.FOAF本體的語(yǔ)義表明FOAF簡(jiǎn)檔是通過(guò)foaf：knows進(jìn)行連接，通過(guò)rdfs：seeAlso添加解釋，所以這種方法可以準(zhǔn)確的找到包含個(gè)人信息的有效FOAF簡(jiǎn)檔.

3.3 RDF數(shù)據(jù)的發(fā)現(xiàn)與解析

FOAF簡(jiǎn)檔是以RDF/XML格式存儲(chǔ)的，如果直接對(duì)其進(jìn)行處理，提取信息的難度會(huì)非常大，并且需要大量的內(nèi)存空間和時(shí)間.我們希望能夠只保留RDF語(yǔ)句中有用的數(shù)據(jù)而去掉大量的標(biāo)簽和符號(hào)，最理想的做法是將其轉(zhuǎn)化為關(guān)系型數(shù)據(jù).使用關(guān)系型數(shù)據(jù)可以很明確的表示出用戶各個(gè)屬性與其他用戶的關(guān)系，同時(shí)程序處理關(guān)系型數(shù)據(jù)更加快速和簡(jiǎn)單.我們使用SPARQL查詢語(yǔ)言實(shí)現(xiàn)了一個(gè)RDF解析器[12]來(lái)處理FOAF簡(jiǎn)檔中的RDF數(shù)據(jù).

SPARQL(Simple protocol and RDF query language)是一種面向RDF的查詢語(yǔ)言，Jena提供了選擇、抽取等關(guān)系數(shù)據(jù)庫(kù)的查詢處理方法，能夠快速地提取RDF文件的信息.RDF解析器可以將RDF屬性和值提取出來(lái)，根據(jù)RDF Schema的信息將RDF三元組分割成若干個(gè)組[13]，同一組的詞放在同一張表中，然后以RDBMS中表格的形式存儲(chǔ)到關(guān)系型數(shù)據(jù)庫(kù)中.最后使用SQL語(yǔ)句執(zhí)行查詢，將不同表中的結(jié)果組合得到最終的結(jié)果.避免直接對(duì)RDF/XML格式的數(shù)據(jù)進(jìn)行操作，能夠有效的降低數(shù)據(jù)處理的復(fù)雜度，提高效率.

抓取FOAF簡(jiǎn)檔和解析數(shù)據(jù)的過(guò)程如圖3所示.

圖3中的Crawler和Parser分別是抓取FOAF簡(jiǎn)檔和解析FOAF簡(jiǎn)檔的工具.Crawler中使用到的SPARQL語(yǔ)句片段1所示：

圖3 FOAF抓取和解析流程Fig.3 FOAF crawling and parsing process

片段1：Crawler解析URL

PREFIX foaf：

PREFIX rdfs：

SELECT ?seeAlso

WHERE {

?x foaf：knows ?knowsPerson.

?knowsPerson rdfs：seeAlso ?seeAlso.

}

其中?seeAlso是可能包含URL的字段，它是FOAF簡(jiǎn)檔中rdfs：seeAlso屬性的值.在FOAF詞匯表的定義中，rdfs：seeAlso屬性表示一個(gè)資源可能提供關(guān)于主題資源的附加信息，一般該屬性的值是一個(gè)站點(diǎn)的URL地址，以rdf：resource來(lái)表示值.這個(gè)查詢中的?knowsPerson字段使用了前綴機(jī)制，當(dāng)FOAF簡(jiǎn)檔中同時(shí)存在foaf：knows和rdfs：seeAlso才會(huì)匹配得到有效的URL.

Parser工具用于提取FOAF簡(jiǎn)檔的其他屬性.Parser中使用到的SPARQL語(yǔ)句如片段2所示：

片段2：Parser解析URL

PREFIX foaf：

SELECT ?(tag)

WHERE{

foaf：(tag) ?(tag).

}

其中tag是一個(gè)變量，在程序中由函數(shù)傳入值，一般tag的值有mbox，weblog，msnChatID等等.該查詢語(yǔ)句會(huì)根據(jù)傳入值的變化而匹配不同的語(yǔ)句.例如，當(dāng)傳入的tag值為knows時(shí)，該查詢將返回?knows的結(jié)果，匹配的是foaf：knows ?knows.其中seeAlso的格式與其他格式不一樣，需要在程序中進(jìn)行額外的判斷.

通過(guò)以上的幾個(gè)步驟，我們可以從RDF數(shù)據(jù)中提取到類似表1所示的數(shù)據(jù)表：

表1 FOAF解析結(jié)果Table 1 FOAF analysis results

通過(guò)關(guān)系數(shù)據(jù)庫(kù)表格之間的聯(lián)系，我們可以得到各個(gè)站點(diǎn)或?qū)嶓w之間的關(guān)聯(lián)情況，據(jù)此計(jì)算用戶的影響力.

4 用戶的影響力計(jì)算及排序

接下來(lái)分析數(shù)據(jù)信息以及整個(gè)網(wǎng)絡(luò)的關(guān)聯(lián)情況.對(duì)于一個(gè)社交網(wǎng)絡(luò)，我們需要掌握用戶站點(diǎn)之間關(guān)聯(lián)的情況，知道哪些用戶是重要的，因此需要計(jì)算站點(diǎn)的重要性并進(jìn)行排序.根據(jù)前面部分的處理，數(shù)據(jù)已經(jīng)形成了以personId代表用戶站點(diǎn)，語(yǔ)義屬性將其它站點(diǎn)關(guān)聯(lián)起來(lái)的模式.通過(guò)分析用戶站點(diǎn)之間的鏈接關(guān)系，找到站點(diǎn)間的依賴關(guān)系.一般來(lái)說(shuō)，一個(gè)站點(diǎn)與越多其他站相關(guān)聯(lián)，其影響力就越大.

在社交網(wǎng)絡(luò)影響力的研究中，最常用的排序算法有PageRank算法和HITS(Hypertext-Induced Topic Search)算法.本文同樣適合使用這兩種方法，因此我們以這兩種方法為原型，做出相應(yīng)的改進(jìn)和變形來(lái)對(duì)處理后的數(shù)據(jù)進(jìn)行分析.

4.1 語(yǔ)義權(quán)值和依賴度

在計(jì)算頁(yè)面重要度的時(shí)候，不僅需要知道哪些頁(yè)面之間存在鏈接，往往還需要根據(jù)內(nèi)容、時(shí)間等不同的特性來(lái)添加權(quán)重因子以得到更加符合實(shí)際情況的結(jié)果，這種方法稱為加權(quán)算法.語(yǔ)義社交網(wǎng)絡(luò)很適合使用加權(quán)計(jì)算，因?yàn)檎军c(diǎn)之間的連接關(guān)系通過(guò)屬性來(lái)表示.每個(gè)站點(diǎn)使用的屬性不同，同時(shí)每個(gè)屬性本身帶有語(yǔ)義，因此站點(diǎn)之間關(guān)聯(lián)程度的強(qiáng)弱也不同.例如，foaf：workIn和foaf：knows表明的關(guān)系程度顯然不一樣，一般情況下foaf：knows要強(qiáng)于foaf：workIn，所以當(dāng)同時(shí)存在這兩種屬性從站點(diǎn)A指向站點(diǎn)B時(shí)，應(yīng)該使用不同的權(quán)值進(jìn)行計(jì)算.因此我們將屬性的語(yǔ)義因素量化成權(quán)值加入站點(diǎn)重要度計(jì)算中.另一方面，站點(diǎn)之間的鏈接情況代表著站點(diǎn)的依賴情況，同樣需要將其量化.在依賴度的計(jì)算中，不考慮鏈接的語(yǔ)義情況，只考慮站點(diǎn)關(guān)聯(lián)的數(shù)量.

我們以統(tǒng)計(jì)方法中的TF-IDF(Term Frequency-Inverse Document Frequency)為基礎(chǔ)，進(jìn)行相應(yīng)的變化得到語(yǔ)義權(quán)值的計(jì)算方法.屬性頻率(Properties Frequency，PF)表示某個(gè)屬性在所有鏈接關(guān)系中被使用的頻繁程度，反向?qū)傩灶l率(Inverse Properties Frequency，IPF)用于平衡屬性的頻率值，我們將使用PF和IPF來(lái)計(jì)算屬性的語(yǔ)義權(quán)值.

對(duì)于一個(gè)語(yǔ)義社交網(wǎng)絡(luò)的站點(diǎn)依賴圖G=(V，E，W)，G是一個(gè)帶權(quán)有向圖，V為站點(diǎn)的集合，E為站點(diǎn)之間聯(lián)系的邊集，W是邊的權(quán)值的集合，則：

(1)

(2)

其中，vi是目標(biāo)站點(diǎn)，p是vi中要計(jì)算頻率的目標(biāo)屬性，f(p，vi)為屬性元素頻率，即vi站點(diǎn)目標(biāo)屬性p出現(xiàn)的次數(shù)與所有屬性次數(shù)的比值.則目標(biāo)站點(diǎn)vi的屬性p的權(quán)值可以由公式(3)得出：

weight(p，vi)=PF(p，vi)×IPF(p，V)

(3)

以上計(jì)算方法中，PF值表示某個(gè)屬性出現(xiàn)的頻率，而IPF表示某個(gè)屬性普遍重要性的度量，最后用兩者的乘積來(lái)表示屬性p的語(yǔ)義權(quán)值.

屬性的語(yǔ)義權(quán)值僅考慮了單獨(dú)站點(diǎn)的影響，并未考慮間接相關(guān)的站點(diǎn)之間的影響，因此還需要計(jì)算站點(diǎn)的依賴度.本文通過(guò)每個(gè)站點(diǎn)中不同屬性所指向的URI之間的聯(lián)系來(lái)量化站點(diǎn)依賴度.同樣對(duì)于帶權(quán)有向圖G，vi站點(diǎn)對(duì)于vj站點(diǎn)的依賴度權(quán)重計(jì)算如下：

(4)

其中，dep(vi，vj)表示依賴度權(quán)重，u表示vj站點(diǎn)依賴的URI，dep(u，vj)表示vj站點(diǎn)對(duì)u的依賴度，它的計(jì)算方法如下：

(5)

(6)

公式(6)中，如果兩個(gè)URI是相關(guān)聯(lián)的，則規(guī)定依賴度為1，反之則為0.其中ulink_tou′表示一個(gè)站點(diǎn)依賴的u與另一個(gè)站點(diǎn)依賴的u′相關(guān)聯(lián)，這種關(guān)聯(lián)關(guān)系可以是直接相關(guān)，也可以是間接相關(guān).以上計(jì)算的含義是，站點(diǎn)vi對(duì)站點(diǎn)vj的依賴度由vi所依賴的URI與vj所依賴的URI的關(guān)聯(lián)情況決定，當(dāng)一個(gè)站點(diǎn)所依賴的URI與另一個(gè)站點(diǎn)所依賴的URI通過(guò)直接或間接的關(guān)聯(lián)越多時(shí)，該站點(diǎn)對(duì)另一個(gè)站點(diǎn)具有越高的依賴度.通過(guò)這種方式將網(wǎng)絡(luò)中其他站點(diǎn)對(duì)目標(biāo)站點(diǎn)的影響程度量化成權(quán)值，在排序的過(guò)程中進(jìn)行加權(quán)的定量計(jì)算.

在確定語(yǔ)義權(quán)值和依賴度權(quán)值的計(jì)算方法之后，我們將其應(yīng)用于影響力計(jì)算和排序中.

4.2 SWPR和SWHITS排序

根據(jù)之前的分析，一個(gè)站點(diǎn)的重要度應(yīng)該由它所依賴屬性的語(yǔ)義權(quán)值和其他相關(guān)站點(diǎn)的依賴度共同決定，因此我們將這兩個(gè)加權(quán)因子加入到了PageRank和HITS算法中，分別稱為語(yǔ)義加權(quán)PageRank(SWPR)算法和語(yǔ)義加權(quán)HITS(SWHITS)算法.

SWPR的含義是，如果某個(gè)站點(diǎn)被越多其他站點(diǎn)依賴，則表明該站點(diǎn)越重要.在計(jì)算過(guò)程中，會(huì)根據(jù)依賴度和相關(guān)屬性的語(yǔ)義因素進(jìn)行加權(quán)運(yùn)算，以sw_PR值作為站點(diǎn)重要性的指標(biāo)，sw_PR值越高代表站點(diǎn)的重要性越大.每個(gè)站點(diǎn)的sw_PR值都會(huì)被迭代計(jì)算若干次，在每一次的計(jì)算中，站點(diǎn)的語(yǔ)義權(quán)值s_weight和依賴度權(quán)值dep都會(huì)被加入，同時(shí)每次迭代計(jì)算后站點(diǎn)的sw_PR值都會(huì)發(fā)生變化，這樣間接相關(guān)的站點(diǎn)對(duì)目標(biāo)站點(diǎn)的影響就加入到了sw_PR值的計(jì)算中.迭代過(guò)程將一直持續(xù)到結(jié)果趨于收斂，最終得到所有站點(diǎn)的sw_PR值，據(jù)此進(jìn)行排序.sw_PR值的計(jì)算規(guī)則如公式(7)所示：

(7)

SWHITS分別從站點(diǎn)的入度和出度兩方面進(jìn)行計(jì)算，入度的大小代表站點(diǎn)被依賴的情況，以sw_Auth值為指標(biāo)，出度的大小代表站點(diǎn)依賴其它站點(diǎn)的情況，以sw_Hubs值為指標(biāo).一個(gè)站點(diǎn)的sw_Auth越大，就表示它被越多的站點(diǎn)依賴，而sw_Hubs值越大則表示它依賴越多的其他站點(diǎn).計(jì)算規(guī)則如公式(8)和公式(9)所示：

(8)

(9)

在計(jì)算中，所有站點(diǎn)初始的sw_Auth(v)值和sw_Hubs(v)值均為1.同樣迭代計(jì)算所有站點(diǎn)的值，每次計(jì)算之后站點(diǎn)的sw_Auth值和sw_Hubs值都將發(fā)生變化.每一次迭代完成后，所有節(jié)點(diǎn)的入度值sw_Auths的平方和需要進(jìn)行標(biāo)準(zhǔn)化，出度值sw_Hubs也是如此，即：

(10)

其中t表示迭代的進(jìn)行的次數(shù)，通過(guò)標(biāo)準(zhǔn)化得到第(t+1)次迭代計(jì)算的值sw_Auth(vi)(t+1)和sw_Hubs(vi)(t+1)，閾值同樣設(shè)定為10-7，在計(jì)算結(jié)果小于該閾值時(shí)得到最終結(jié)果.

這兩種排序算法中，以sw_PR值得到結(jié)果與以sw_Auth值得到的結(jié)果比較接近，因?yàn)檫@兩種方法都是根據(jù)站點(diǎn)被其它站點(diǎn)依賴的情況進(jìn)行計(jì)算.SWPR排序的優(yōu)點(diǎn)在于最終的結(jié)果與實(shí)際更接近，而SWHITS排序可以知道站點(diǎn)的中心性和樞紐性情況.在原始的HITS算法中存在TKC現(xiàn)象(Tightly Knit Community effect)，即如果一個(gè)網(wǎng)絡(luò)中部分站點(diǎn)形成了一個(gè)內(nèi)聚度很高的簇，則會(huì)導(dǎo)致這個(gè)簇中的節(jié)點(diǎn)在排名中會(huì)有很高的Auth值和Hubs值.它們這些特點(diǎn)可以作為最終排序結(jié)果的準(zhǔn)確性的參考標(biāo)準(zhǔn)之一.

5 實(shí)驗(yàn)與分析

實(shí)驗(yàn)用Java語(yǔ)言編寫，在JDK1.8.0的環(huán)境下運(yùn)行.實(shí)驗(yàn)所用到的核心工具包括FOAF簡(jiǎn)檔解析依賴的Apache Jena 2.1.1和關(guān)系型數(shù)據(jù)庫(kù)工具jdbc及mysql相關(guān)的jar包.數(shù)據(jù)來(lái)源于國(guó)外的一個(gè)規(guī)模較大的語(yǔ)義社交網(wǎng)站Advogato(http：//www.advogato.org).該網(wǎng)站是一個(gè)軟件開發(fā)者用于交流和分享的平臺(tái)，為所有用戶站點(diǎn)和項(xiàng)目提供了FOAF簡(jiǎn)檔，可用于群體信任度量和其他社交網(wǎng)絡(luò)技術(shù)的研究測(cè)試.

5.1 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)爬取了21360個(gè)FOAF簡(jiǎn)檔，包含82149個(gè)用戶，101025條關(guān)系和2413個(gè)FOAF屬性.在解析RDF文檔時(shí)我們對(duì)一些不重要的屬性進(jìn)行了刪除，即在101025條關(guān)系中出現(xiàn)次數(shù)小于101次的屬性(實(shí)際上很多屬性都只出現(xiàn)過(guò)幾次).由于社交網(wǎng)絡(luò)具有大量的無(wú)效用戶，為了計(jì)算方便，我們僅保留了4295個(gè)有效用戶和46812條關(guān)系.同時(shí)使用了基于認(rèn)知語(yǔ)言學(xué)的WordNet詞典對(duì)重復(fù)站點(diǎn)和同義屬性進(jìn)行了合并，最終剩下25個(gè)常用的屬性.

最終的排序結(jié)果分別如下所示(只展示排名最前的7位，保留5位小數(shù)).

表2 影響力排序結(jié)果Table 2 Influence ranking results

我們對(duì)排序結(jié)果進(jìn)行了分析.從表2中可以看到用戶federico，alan，miguel，rms，raph都出現(xiàn)在SWPR和SWHITS (Auths)排序的前7位中.經(jīng)過(guò)查找，我們發(fā)現(xiàn)這些用戶都是該網(wǎng)站中非常受歡迎的博主、項(xiàng)目的負(fù)責(zé)人或技術(shù)專家.他們擁有大量的關(guān)注者，很多用戶的FOAF簡(jiǎn)檔中都會(huì)指向他們的站點(diǎn)、主頁(yè)、文章和項(xiàng)目等，因而這些站點(diǎn)具有很高的SWPR值和sw_Auths值，他們?cè)谏缃痪W(wǎng)絡(luò)中有很大的影響力.而SWHITS(Hubs)中排名靠前的用戶是網(wǎng)站中活躍度很高的用戶，他們關(guān)注了很多用戶和項(xiàng)目，他們的FOAF簡(jiǎn)檔關(guān)聯(lián)了很多用戶站點(diǎn)或URI，因而這些站點(diǎn)有很高的sw_Hubs值.實(shí)驗(yàn)結(jié)果與實(shí)際相符，證明該方法能夠得到正確的結(jié)果.

5.2 對(duì)比分析

由于受到人的主觀因素和各種其他因素的影響，網(wǎng)頁(yè)最終排序結(jié)果的好壞往往沒有固定的標(biāo)準(zhǔn)，大部分時(shí)候還是需要人為的查找實(shí)際數(shù)據(jù)進(jìn)行驗(yàn)證.在其他的工作中已經(jīng)有研究者用其提出的方法對(duì)收集到的數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)和分析，為了檢驗(yàn)本文方法的有效性，我們將使用其他工作中的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，我們分別從以下兩個(gè)方面將本文方法與其他方法進(jìn)行對(duì)比.

1)發(fā)現(xiàn)的有效FOAF簡(jiǎn)檔占所有文檔的百分比，對(duì)比結(jié)果如圖4所示.

圖4 有效的FOAF簡(jiǎn)檔個(gè)數(shù)Fig.4 Number of valid FOAF profiles

從圖4中可以看出，直接通過(guò)語(yǔ)義社交網(wǎng)絡(luò)鏈接模型獲取FOAF簡(jiǎn)檔的有效率約為72.5%，而本文的特征模式發(fā)現(xiàn)可以達(dá)到91.8%，其中無(wú)效的部分大都是只有FOAF的定義模式而并沒有任何數(shù)據(jù)的空白文檔.有效率的提高表明，相比于原來(lái)的方法，本文的特征模式考慮了FOAF簡(jiǎn)檔的結(jié)構(gòu)特征和語(yǔ)義特征，能夠更加準(zhǔn)確的篩選出有效的簡(jiǎn)檔，過(guò)濾掉非個(gè)人信息的FOAF簡(jiǎn)檔.有效數(shù)據(jù)占比的增加能夠提高數(shù)據(jù)處理的效率和結(jié)果的可信度，同時(shí)也驗(yàn)證了該方法的可行性和有效性.

2)在評(píng)判語(yǔ)義權(quán)值與依賴度排序算法時(shí)，我們選用文獻(xiàn)[15,16]中的幾種排序方法進(jìn)行對(duì)比，這些方法都只考慮兩個(gè)站點(diǎn)之間不同的關(guān)聯(lián)結(jié)構(gòu)而沒有考慮屬性的語(yǔ)義特征和整體的依賴關(guān)系.通過(guò)計(jì)算用戶站點(diǎn)之間的信任度來(lái)表示站點(diǎn)的重要性，我們采用NDCG(Normalized Discounted Cumulative Gain)來(lái)評(píng)判信任度的高低.NDCG一般用于評(píng)價(jià)搜索系統(tǒng)中排序的結(jié)果，它要考慮搜索結(jié)果的召回率和相關(guān)率.NDCG的定義為：

(11)

(12)

其中，reli表示第i個(gè)站點(diǎn)的信任度，p表示站點(diǎn)數(shù)量，IDCGp表示完美排序下DCGp的結(jié)果，最終NDCG的結(jié)果將在0-1之間，且值越大準(zhǔn)確率越高.完美排序結(jié)果通過(guò)分別計(jì)算每一個(gè)目標(biāo)站點(diǎn)的關(guān)系得出以盡量接近最準(zhǔn)確的結(jié)果，信任度則根據(jù)屬性語(yǔ)義的強(qiáng)弱賦予不同的系數(shù)，由于屬性語(yǔ)義的強(qiáng)弱只能由人判定，因此我們?yōu)槠浞峙淞?-1之間不同的系數(shù).

基于以上的評(píng)判準(zhǔn)則，我們使用三種方法中結(jié)果相對(duì)更準(zhǔn)確的SWPR算法進(jìn)行計(jì)算.對(duì)若干個(gè)站點(diǎn)分別使用SWPR和文獻(xiàn)[14,15]中使用的幾種方法進(jìn)行排序，然后使用NDCG進(jìn)行打分，結(jié)果如表3所示.

表3 NDCG結(jié)果Table 3 NDCG results

其中k代表計(jì)算站點(diǎn)的數(shù)量.從表中可以看出SWPR算法具有更高的分?jǐn)?shù)，雖然語(yǔ)義權(quán)值的度量本身存在人為因素，但在語(yǔ)義關(guān)系強(qiáng)弱一致的情況下，最終的結(jié)果仍然保持穩(wěn)定，因此我們可以認(rèn)為SWPR具有更好的效果.

6 結(jié)束語(yǔ)

隨著社交網(wǎng)絡(luò)的迅速發(fā)展，語(yǔ)義社交網(wǎng)絡(luò)提出了一種高度結(jié)構(gòu)化與高可信度的模式，對(duì)其特征的分析研究和構(gòu)建更健全的社交系統(tǒng)具有非常重要的意義.用戶影響力的計(jì)算和分析對(duì)研究社交網(wǎng)絡(luò)演化、個(gè)體行為特征、信息傳播模式等問題都有很大的幫助.本文主要介紹了從語(yǔ)義社交網(wǎng)絡(luò)中發(fā)現(xiàn)用戶站點(diǎn)，提取和處理用戶信息，并根據(jù)用戶的語(yǔ)義關(guān)系計(jì)算影響力大小從而進(jìn)行排序的方法及其實(shí)現(xiàn).其中每一個(gè)部分都可以作為獨(dú)立的模塊應(yīng)用在其他相關(guān)的研究工作中.實(shí)驗(yàn)結(jié)果顯示，該方法能夠很好的處理語(yǔ)義社交網(wǎng)絡(luò)的數(shù)據(jù)和信息，準(zhǔn)確的分析出網(wǎng)絡(luò)中用戶和實(shí)體的關(guān)聯(lián)情況.

本文的方法還有改進(jìn)的地方，下一步的工作主要包括：進(jìn)一步優(yōu)化社交網(wǎng)絡(luò)的鏈接模型，對(duì)FOAF簡(jiǎn)檔的特征模式進(jìn)行改進(jìn)，找到更準(zhǔn)確的用戶關(guān)系；考慮用戶屬性的個(gè)性化和多元化，改進(jìn)語(yǔ)義屬性合并算法；考慮不同屬性的語(yǔ)義，調(diào)整排序算法中權(quán)值和出入度的計(jì)算方法，提高排序的準(zhǔn)確度.