圖數(shù)據(jù)挖掘在社交網(wǎng)絡(luò)的應(yīng)用研究
2016-05-17 11:18:20貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院朋貴州大學(xué)大數(shù)據(jù)學(xué)院高建瓴
電子世界 2016年8期
貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 閆 朋貴州大學(xué)大數(shù)據(jù)學(xué)院 高建瓴
?
圖數(shù)據(jù)挖掘在社交網(wǎng)絡(luò)的應(yīng)用研究
貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 閆 朋
貴州大學(xué)大數(shù)據(jù)學(xué)院 高建瓴
【摘要】社交網(wǎng)絡(luò)數(shù)據(jù)的復(fù)雜性為數(shù)據(jù)挖掘帶來嚴(yán)峻的考驗(yàn)，對(duì)于數(shù)據(jù)的復(fù)雜性，在社交網(wǎng)絡(luò)中使用具有針對(duì)性的處理方法顯得尤為重要。圖數(shù)據(jù)挖掘依據(jù)圖數(shù)據(jù)關(guān)系，可以很好地利用其本有的優(yōu)勢(shì)來開發(fā)和分析這類互相聯(lián)系緊密的實(shí)體聯(lián)系的復(fù)雜數(shù)據(jù)。該文根據(jù)圖數(shù)據(jù)挖掘的特性和圖數(shù)據(jù)挖掘的處理方式，首先介紹了圖數(shù)據(jù)挖掘方面的若干定義、計(jì)算模型以及在圖數(shù)據(jù)挖掘方面的處理系統(tǒng)；然后介紹了圖數(shù)據(jù)挖掘的應(yīng)用，主要包括圖數(shù)據(jù)庫的相關(guān)內(nèi)容以及圖數(shù)據(jù)算法等；最后，從整體上簡(jiǎn)要介紹了社交網(wǎng)絡(luò)的發(fā)展情況以及圖數(shù)據(jù)挖掘與社交網(wǎng)絡(luò)的的不同模型不同的結(jié)合過程和處理方法。
【關(guān)鍵詞】圖數(shù)據(jù)挖掘算法；圖數(shù)據(jù)庫；MapReduce；Neo4J；頻繁模式
0 引言
近年來社交網(wǎng)絡(luò)風(fēng)靡全球，隨之產(chǎn)生了大量關(guān)系復(fù)雜的關(guān)系型數(shù)據(jù)，如何處理這些關(guān)系型數(shù)據(jù)成為數(shù)據(jù)挖掘行業(yè)的熱門研究課題。在社交網(wǎng)絡(luò)的數(shù)據(jù)挖掘中，對(duì)社交媒體中各實(shí)體和聯(lián)系進(jìn)行詳細(xì)的分析，不僅能夠準(zhǔn)確的理解各個(gè)實(shí)體的關(guān)系與實(shí)體的內(nèi)在特點(diǎn)，還可以根據(jù)實(shí)體之間的聯(lián)系為商業(yè)規(guī)劃、災(zāi)情控制、輿論的預(yù)防等做出相應(yīng)的決策。圖數(shù)據(jù)挖掘，依據(jù)圖數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢(shì)，在處理大量的社交關(guān)系的數(shù)據(jù)時(shí)，可以很好的發(fā)揮數(shù)據(jù)挖掘的優(yōu)勢(shì)。本文從圖數(shù)據(jù)挖掘方面的定義等理論研究?jī)?nèi)容、圖數(shù)據(jù)挖掘在具體的應(yīng)用研究方面的狀況以及圖數(shù)據(jù)挖掘在社交網(wǎng)絡(luò)的具體應(yīng)用三個(gè)方面來對(duì)圖數(shù)據(jù)挖掘在社交網(wǎng)絡(luò)的應(yīng)用研究做出詳細(xì)的說明。
1 圖數(shù)據(jù)挖掘理論研究
圖數(shù)據(jù)挖掘，因其在處理圖數(shù)據(jù)方面的優(yōu)勢(shì)，廣泛的應(yīng)用在生物信息學(xué)、Web挖掘、網(wǎng)格計(jì)算、社交媒體中。本節(jié)結(jié)合圖數(shù)據(jù)挖掘在社交網(wǎng)絡(luò)的具體應(yīng)用，列出了圖數(shù)據(jù)挖掘方面的理論研究?jī)?nèi)容，主要包括圖數(shù)據(jù)挖掘方面的定義、計(jì)算模型和處理系統(tǒng)。
1.1圖數(shù)據(jù)挖掘定義
定義1：圖。圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間的邊的集合所組成，通常表示方式為：G=(V，E)。其中，G表示-個(gè)圖，V是該圖中頂點(diǎn)的集合，E是該圖中邊的集合。若?<φ，ψ>∈E，則<φ，ψ>表示從φ到ψ的弧，φ稱為弧尾，ψ稱為弧頭。
定義2：有向圖。若圖G（V，E），其中E中的邊以兩個(gè)頂點(diǎn)表示，如果這兩個(gè)頂點(diǎn)之間是有順序的，即?<φ，ψ>∈E，那么該圖是有向圖。如果這個(gè)頂點(diǎn)之間是沒有順序的，即?<φ，ψ>∈E必有?<ψ，φ>E，則該圖是無向圖。
定義3：確定圖。確定圖G被表示為G=（（V，E），∑V，∑E，L），其中V是頂點(diǎn)集，E是邊集，（V，E）是-個(gè)無向圖，E?V×V是圖G的邊集合，∑V和∑E分別是圖G的節(jié)點(diǎn)符號(hào)集和邊標(biāo)號(hào)集合，L是標(biāo)號(hào)的映射函數(shù)。
定義4：不確定圖。不確定圖G可以表示為G（（V，E）∑V，∑E，L，P），其中V是頂點(diǎn)集，E是邊集，（V，E）是-個(gè)無向圖，E?V×V是圖G的邊集合，∑E和∑V分別是邊的標(biāo)號(hào)的集合以及節(jié)點(diǎn)符號(hào)的集合，L對(duì)于標(biāo)號(hào)是映射函數(shù)，P對(duì)于邊是可能性函數(shù)，范圍在（0，1]。當(dāng)邊的存在可能性為1表示邊-定存在。確定圖是邊存在可能性為1的特殊的不確定圖。
定義5：子圖。兩個(gè)圖G1=（V1，E1），G2=（V2，E2），對(duì)于?V2?V1且E2?E1，則稱G2是G1的子圖。
定義6：圖同構(gòu)。假設(shè)圖設(shè)G1=（V1，E1），G2=（V2，E2）為兩個(gè)無向圖(兩個(gè)有向圖)，若存在雙射函數(shù)f：V1→V2，對(duì)于?Vx，Vy∈V1，(Vx，Vy)∈E1(
定義7：圖數(shù)據(jù)挖掘。圖數(shù)據(jù)挖掘是從圖數(shù)據(jù)庫中大量的數(shù)據(jù)中找出隱含的模式、特征、規(guī)律和知識(shí)，并用于分類和其他方面。圖數(shù)據(jù)挖掘有數(shù)據(jù)圖和模式圖兩類構(gòu)成。其中，數(shù)據(jù)圖是以數(shù)據(jù)節(jié)點(diǎn)為基礎(chǔ)來進(jìn)行分析圖，模式圖是以數(shù)據(jù)整個(gè)關(guān)系模型來進(jìn)行分析數(shù)據(jù)。
1.2圖數(shù)據(jù)挖掘計(jì)算模型
隨著社交網(wǎng)絡(luò)的大力發(fā)展和圖數(shù)據(jù)應(yīng)用面的推廣，圖數(shù)據(jù)量激增，對(duì)于圖數(shù)據(jù)挖掘的處理分析提出了嚴(yán)峻的考驗(yàn)。在圖數(shù)據(jù)挖掘中本小節(jié)根據(jù)圖數(shù)據(jù)的不同情況，采用不同的計(jì)算模型來進(jìn)行圖數(shù)據(jù)挖掘的探討。
圖1 MapReduce架構(gòu)圖
（1）MapReduce
在現(xiàn)階段云計(jì)算、大數(shù)據(jù)技術(shù)流行的今天，MapReduce數(shù)據(jù)處理模型是最受歡迎的計(jì)算模型之-。MapRduce[1]采用了Master/Slave（M/ S）架構(gòu)，MapReduce架構(gòu)如圖1所示，它主要有Task、TaskTracker、JobTracker、client等組成。用戶在使用的時(shí)候通過客戶端把MP程序提交給JobTracker，然后以客戶端接口的形式查看job的運(yùn)行情況。對(duì)于資源的監(jiān)控和job的調(diào)度由JobTracker負(fù)責(zé)。TaskTracker節(jié)點(diǎn)上資源的使用請(qǐng)和job的運(yùn)行進(jìn)度，由TaskTracker負(fù)責(zé)，TaskTracker以本節(jié)點(diǎn)上的心跳機(jī)制發(fā)送給JobTracker，并且接收J(rèn)obTracker的反饋情況。
MapReduce的執(zhí)行流程如下所示：1）Job的提交和初始化。JobTracker實(shí)例在接收到用戶的提交請(qǐng)求后，將任務(wù)分發(fā)到分布式系統(tǒng)的各個(gè)節(jié)點(diǎn)上，JobTracker在通過RPC獲得通知后，對(duì)新的Job進(jìn)行初始化。2）任務(wù)調(diào)度與監(jiān)控。3）作業(yè)運(yùn)行環(huán)境的準(zhǔn)備工作。包括JVM的啟動(dòng)以及資源的隔離。4）任務(wù)的執(zhí)行。TaskTracker為Task準(zhǔn)備好運(yùn)行環(huán)境后，便會(huì)啟動(dòng)Task。5）結(jié)束作業(yè)。當(dāng)所有的任務(wù)運(yùn)行結(jié)束后，整個(gè)Job的執(zhí)行流程就顯示成功結(jié)束。
MapReduce處理的圖數(shù)據(jù)-般位于分布式文件系統(tǒng)中，該系統(tǒng)往往將用戶的文件切分成若干個(gè)固定大小的block存儲(chǔ)到不同節(jié)點(diǎn)上。然而，該計(jì)算模型在擴(kuò)展性、容錯(cuò)性和多框架支持方面存在不足，特別是在對(duì)于需要迭代計(jì)算的算法，MapReduce顯然不可用，迭代n次的IO量太大，BSP模型的優(yōu)勢(shì)就顯示出來了。
（2）BSP
BSP是由英國(guó)著名的科學(xué)家Viliant創(chuàng)立以架起計(jì)算機(jī)程序語言和體系結(jié)構(gòu)為目的，具有模塊、選錄器、同步路張琪三個(gè)特性的并行計(jì)算模型[2]。它主要有-組具有局部?jī)?nèi)存的分布式處理器、全局?jǐn)?shù)據(jù)通訊網(wǎng)絡(luò)和支持所有處理單元間全局路障同步的機(jī)制組成。不同于MapReduce那樣對(duì)全體數(shù)據(jù)進(jìn)行的拷貝操作，BSP的并行task之間通過消息來共享中間結(jié)果。簡(jiǎn)要的來講，就是將求解問題抽象成圖模型（頂點(diǎn)Vertex、邊Edge）后，再通過消息Message，來不斷迭代求解。
（3）Spark GraphX
Spark GraphX是-個(gè)基于Spark平臺(tái)的分布式圖處理框架，它通過提供對(duì)圖計(jì)算和圖挖掘簡(jiǎn)潔易用且豐富的接口，為圖處理請(qǐng)求帶來了極大的方便性。graphx使用的是vertexcut(點(diǎn)分割)方式存儲(chǔ)圖，并將graph-parallel和data-parallel統(tǒng)-到-個(gè)系統(tǒng)中，這個(gè)系統(tǒng)擁有-個(gè)唯-的組合API。GraphX還允許用戶將數(shù)據(jù)當(dāng)做-個(gè)圖和-個(gè)集合（RDD），而不需要數(shù)據(jù)移動(dòng)或者復(fù)制，通過將最新的進(jìn)展整合進(jìn)graph-parallel系統(tǒng)，GraphX能夠優(yōu)化圖操作的執(zhí)行。
1.3圖數(shù)據(jù)挖掘處理系統(tǒng)
（1）Twister
Twister[3]是-個(gè)基于MapReduce的專用迭代式計(jì)算的輕量級(jí)圖數(shù)據(jù)處理系統(tǒng)，通過合并增強(qiáng)MapReduce的編程模型和改進(jìn)體系結(jié)構(gòu)功能，Twister得到了快速的發(fā)展。對(duì)于圖數(shù)據(jù)挖掘算法，有大部分是基于迭代計(jì)算的，這與Twister系統(tǒng)的系統(tǒng)結(jié)構(gòu)的作用原理相似，用Twister來進(jìn)行圖數(shù)據(jù)的處理可以達(dá)到很好的處理效果。Twister提供以下功能來支持MR運(yùn)算進(jìn)行圖數(shù)據(jù)挖掘處理：
區(qū)別于靜態(tài)數(shù)據(jù)和可變數(shù)據(jù)；
可配置長(zhǎng)期運(yùn)行的map/reduce任務(wù)；
基于發(fā)布/訂閱消息傳遞的通信數(shù)據(jù)機(jī)制，有效的支持迭代MapReduce計(jì)算，處理速度極快于DryadLINQ；支持典型的MapReduce計(jì)算工具來管理數(shù)據(jù)。除此之外，還具有以下新特性：
ActiveMQ支持新的代理軟件，其主要是用于消息的處理，她是-個(gè)獨(dú)立的模塊；
當(dāng)FaultTolerance不可用，自動(dòng)啟動(dòng)故障恢復(fù)機(jī)制；
分區(qū)文件可以在客戶機(jī)代碼塊中被創(chuàng)建。
（2）Haloop
與Twister類似HaLoop[4]也是在MapReduce框架的基礎(chǔ)上進(jìn)行改進(jìn)從而來更好地支持迭代計(jì)算的數(shù)據(jù)分析任務(wù)系統(tǒng)。HaLoop對(duì)MapReduce改進(jìn)體現(xiàn)在提供了-套可以支持迭代式處理程序的編程接口，使得任務(wù)調(diào)度對(duì)于迭代操作敏感，將loop-invariant data 放在reduce節(jié)點(diǎn)的cache上，可以提升性能，并且Haloop的基本思想是緩存循環(huán)不變量到salve nodes，每次迭代都加載這些數(shù)據(jù)，從而使得處理速度和性能得到顯著提升，也使得它適合做離線計(jì)算。它的配置與Hadoop完全相同，除了沒有單機(jī)模式和為分布式模式，命令選項(xiàng)也與Hadoop相同。
（3）Pregel
Pregel是-個(gè)用于分布式圖計(jì)算的計(jì)算框架，主要用于圖遍歷（BFS）、最短路徑（SSSP）、PageRank計(jì)算等。它是Google圖算法引擎，采用BSP計(jì)算模型來完成迭代的同步問題[5][6]，即采用：“計(jì)算-通信-同步”的模式，輸入為有向圖，分成超步，以節(jié)點(diǎn)為中心進(jìn)行計(jì)算，超步內(nèi)每個(gè)節(jié)點(diǎn)執(zhí)行自己的任務(wù)，執(zhí)行節(jié)點(diǎn)的順序不確定，兩個(gè)超步之間是通信階段。
（4）Hama
Hama[7][8][9]也是-個(gè)基于BSP開源的針對(duì)圖數(shù)據(jù)處理的分布式系統(tǒng)，雖然發(fā)展時(shí)間很短，但其良好的圖數(shù)據(jù)處理性能已得到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。Hama提供的是純BSP模型，支持消息傳遞與全局通信，由-系列超步組成，每個(gè)超步包括本地計(jì)算、進(jìn)程通信、障柵同步。它通過繼承org.apache.hama.bsp.BSP類來創(chuàng)建自己的BSP類，并提供了Graph包，支持頂點(diǎn)為中心的圖計(jì)算，使用較少的代碼就可以實(shí)現(xiàn)google Pregel風(fēng)格的應(yīng)用。
（5）Trinity
Trinity[10]微軟的圖計(jì)算平臺(tái)，由C#語言開發(fā)完成，是-個(gè)專用的圖計(jì)算應(yīng)用平臺(tái)，包括底層的存儲(chǔ)到上層的應(yīng)用。它是可以實(shí)現(xiàn)BSP模型的，包含-個(gè)建立字分布式內(nèi)存云平臺(tái)上的圖數(shù)據(jù)庫及-個(gè)計(jì)算框架，通過-個(gè)純內(nèi)存的key-value存儲(chǔ)數(shù)據(jù)庫實(shí)現(xiàn)快速訪問。Trinity的-個(gè)基本存儲(chǔ)單元稱為-個(gè)cell，每個(gè)cell通過-個(gè)全局唯-的id標(biāo)示，該id是-個(gè)64位的整數(shù)，支持用戶通過這個(gè)id進(jìn)行隨機(jī)訪問。從底層key-value的存儲(chǔ)角度來看，key就是cell-id，value是-個(gè)任意長(zhǎng)度的字符串。
（6）Arbor
它是基于BSP的圖數(shù)據(jù)處理平臺(tái)[11]，對(duì)BSP進(jìn)行了改進(jìn)和優(yōu)化，主要體現(xiàn)在取消迭代間的大同步與優(yōu)化消息中間件，支持實(shí)時(shí)圖數(shù)據(jù)的處理，可以進(jìn)行圖數(shù)據(jù)的組織、處理，對(duì)于大規(guī)模圖task可以快速的運(yùn)行。
2 圖數(shù)據(jù)挖掘的應(yīng)用研究
2.1圖數(shù)據(jù)庫
圖數(shù)據(jù)庫-個(gè)完全不同于關(guān)系型數(shù)據(jù)庫的新型數(shù)據(jù)庫，它處理的是大規(guī)模的數(shù)據(jù)和不斷變化的需求，使用的是圖結(jié)構(gòu)、節(jié)點(diǎn)、邊、屬性等存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)庫。在社交網(wǎng)絡(luò)中節(jié)點(diǎn)代表著人（或其可以相互交往的其它媒介，可以是某個(gè)團(tuán)體，也可以是某個(gè)可以交往的實(shí)物），邊代表著社交網(wǎng)絡(luò)中的人與人之間的聯(lián)系。當(dāng)前使用情況比較好的圖數(shù)據(jù)庫主要有Neo4J、Infinite Graph、Dex、InfoGrid、HyperGraphDB、VertexDB、Sones等。
Neo4J[12][13]由Neo Technology開發(fā)的開源圖數(shù)據(jù)庫，該公司從2000年起就開始研發(fā)圖數(shù)據(jù)庫，在圖數(shù)據(jù)庫產(chǎn)品的研發(fā)上面處于領(lǐng)先地位，思科，惠普，德意志電信等跨國(guó)企業(yè)均是它客戶。它采用直觀的圖模型存儲(chǔ)和基于磁盤的持久存儲(chǔ)，具有高可用的分布式集群，是-個(gè)用Java實(shí)現(xiàn)、完全兼容ACID的圖形數(shù)據(jù)庫。Neo4j的內(nèi)核是-種極快的圖形引擎，具有數(shù)據(jù)庫產(chǎn)品期望的所有特性，如恢復(fù)、兩階段提交、符合XA等。
Infinite Graph是-款由Objectivity公司推出的圖形類數(shù)據(jù)庫，該公司還推出過-款同名的對(duì)象類數(shù)據(jù)庫。InfiniteGraph需要作為服務(wù)項(xiàng)目加以安裝，這與以MySQL為代表的傳統(tǒng)數(shù)據(jù)庫頗為相似。InfiniteGraph借鑒了Objectivity/DB中的面向?qū)ο蟾拍睿虼似渲械拿?個(gè)節(jié)點(diǎn)及邊線都算作-個(gè)對(duì)象，尤其是所有節(jié)點(diǎn)類都將擴(kuò)展BaseVertex基本類和所有邊線類都將擴(kuò)展BaseEdge基本類。DEX是-款具備高性能及優(yōu)秀可擴(kuò)展性的圖形類數(shù)據(jù)庫，最多可支持100萬個(gè)節(jié)點(diǎn)，同時(shí)支持java和.Net編程。HyperGraphDB是-套開源數(shù)據(jù)存儲(chǔ)機(jī)制，依托于BerkeleyDB數(shù)據(jù)庫存在。HyperGraphDB的圖形模型是直接式超圖形。從數(shù)學(xué)角度來講，超圖形允許其-條邊線指向兩個(gè)以上的節(jié)點(diǎn)，相比其他圖形類數(shù)據(jù)庫能夠處理更多復(fù)雜結(jié)構(gòu)[14]。InfoGrid是-款“網(wǎng)頁圖形數(shù)據(jù)庫”，它的某些功能主要面向網(wǎng)頁應(yīng)用程序，InfoGrid在OpenID項(xiàng)目中也擁有幾款應(yīng)用程序，該項(xiàng)目同樣由Netmesh公司所支持。
2.2圖數(shù)據(jù)挖掘算法與實(shí)現(xiàn)
圖數(shù)據(jù)挖掘算法作為圖數(shù)據(jù)挖掘的核心內(nèi)容，在圖數(shù)據(jù)挖掘過程中起著決定性的作用。目前，圖數(shù)據(jù)挖掘算法分為圖查詢、圖聚類、圖分類和圖的頻繁子圖挖掘這四大類算法。
2.2.1圖查詢算法
對(duì)于圖查詢問題，R.Giugno[15]等人提出以路徑作為特征結(jié)構(gòu)建立索引的GraphGreP算法；X.Yan[16]等人提出了利用頻繁子圖作為關(guān)鍵特征索引的Glndex算法；S.Zhang[17]等人提出的利用生成樹作為索引結(jié)構(gòu)的TreePi算法；P.Zhao[18]等人提出了以樹結(jié)構(gòu)為主、以判斷圖為輔的Tree+△算法。對(duì)于大圖上的可達(dá)性查詢，R.Agrawal[19]等人最早提出了基于區(qū)間編碼的索引方法；S.Triβ[20]對(duì)基于區(qū)間的索引方法進(jìn)行改進(jìn)得到GRIPP算法。
2.2.2圖聚類算法
圖聚類的目的是將基于圖結(jié)構(gòu)具有相似性的各頂點(diǎn)劃分到集群中，這些頂點(diǎn)在-個(gè)集群中或者相互之間具有連接關(guān)系。圖聚類在基于集群的識(shí)別方面分為兩大類，分別為計(jì)算預(yù)定義的結(jié)點(diǎn)之間的距離和找出最優(yōu)聚類比的聚類。圖聚類算法主要分為劃分方法、層次方法以及幾何形成的最小生成樹聚類（GMC）算法[21]。在劃分方法中，最常用的劃分方法為k-means[22]算法和k中心點(diǎn)算法[22]。相應(yīng)地，層次方法由凝聚層次算法和分裂層次算法這兩種構(gòu)成。
2.2.3圖分類算法
圖分類分為以FSG[23]算法為主要代表的圖特征提取的方法和以CPK分類算法為主的圖核函數(shù)[24-26]這兩類分類方法[27]。圖分類算法是在數(shù)據(jù)挖掘的分類算法的基礎(chǔ)上發(fā)展興起的，分類算法從單-的分類方法中分為決策樹、貝葉斯、人工網(wǎng)絡(luò)、K-近鄰等，以及組合單-分類方法的集成算法如Bagging和Boosting等。通過對(duì)這些算法結(jié)合圖的特性進(jìn)行改進(jìn)，使之更好的適合圖數(shù)據(jù)挖掘的需求。
2.2.4 頻繁子圖挖掘算法
頻繁子圖挖掘算法主要有三種分類方式，第-種是按照模式挖掘算法的輸入類型分為graph-tranction和single-graph兩種類型；第二種，按照采用度量的不同，分為支持度、支持度-置信度、MDL三種；第三種，按照挖掘出的頻繁子圖的類型分為-般子圖、連通子圖、誘導(dǎo)子圖。但是這些分發(fā)它們的思路都是以遞歸為基礎(chǔ)，挖掘出所有頻繁子圖，從而挖掘出所有的頻繁集[28]。
3 圖數(shù)據(jù)挖掘在社交網(wǎng)絡(luò)的應(yīng)用
社交網(wǎng)絡(luò)作為互聯(lián)網(wǎng)媒體主要的交友、交流以及進(jìn)行資源共享、信息的傳遞平臺(tái)，對(duì)其進(jìn)行挖掘使其更加符合用戶的需求就變的很重要。要做到這點(diǎn)，就須要結(jié)合圖數(shù)據(jù)挖掘的特性，進(jìn)行針對(duì)性的數(shù)據(jù)分類、分析等各種研究。
3.1圖數(shù)據(jù)挖掘在社交網(wǎng)絡(luò)的背景和意義
從社交網(wǎng)絡(luò)興起到現(xiàn)階段社交網(wǎng)絡(luò)的廣泛使用，社交網(wǎng)絡(luò)的數(shù)據(jù)已經(jīng)有-個(gè)指數(shù)級(jí)的增長(zhǎng)，數(shù)據(jù)也從單-的字符型的結(jié)構(gòu)化數(shù)據(jù)增加到有音頻、視頻等多媒體的非結(jié)構(gòu)數(shù)據(jù)，這些數(shù)據(jù)都是隨著人們的表達(dá)和互動(dòng)的方式而產(chǎn)生和改變。社交網(wǎng)絡(luò)對(duì)當(dāng)今人們?cè)诨ヂ?lián)網(wǎng)溝通方式等方面具有很大的影響，比如如何在微博上搜索到自己感興趣方面的話題，以及哪些名人對(duì)這類話題感興趣，通過向這些在某方面有經(jīng)驗(yàn)的人學(xué)習(xí)，提高自己的知識(shí)修養(yǎng)，這些是傳統(tǒng)的互聯(lián)網(wǎng)工具做不到的。社交網(wǎng)絡(luò)已經(jīng)深入到各個(gè)不同的行業(yè)，通過對(duì)社交網(wǎng)絡(luò)相關(guān)領(lǐng)域的研究（如在社交網(wǎng)絡(luò)中進(jìn)行社會(huì)搜索、社會(huì)關(guān)系查詢擴(kuò)張的控制、語義web、語以導(dǎo)航等），從而可以選擇正確的信息提取方法和技術(shù)獲得高質(zhì)量、豐富的信息來源。通過對(duì)社交網(wǎng)絡(luò)進(jìn)行圖數(shù)據(jù)挖掘，可以從文本、音頻、視頻等結(jié)構(gòu)化和非結(jié)構(gòu)化數(shù)據(jù)中提取信息網(wǎng)絡(luò)交流內(nèi)容、短消息內(nèi)容、朋友與朋友的文檔、觀察面對(duì)面的通信等不同類型的過濾和分析型的數(shù)據(jù)。
社交網(wǎng)絡(luò)是-個(gè)復(fù)雜數(shù)據(jù)關(guān)系集合，使用傳統(tǒng)的數(shù)據(jù)挖掘方式在處理這類數(shù)據(jù)時(shí)，增加了查詢、分類等的復(fù)雜度，而使用圖進(jìn)行處理就可以很好的解決關(guān)系型問題帶來的不足之處。社交網(wǎng)絡(luò)屬于復(fù)雜網(wǎng)絡(luò)，其本身可以看做為-個(gè)大的數(shù)據(jù)圖，使用圖數(shù)據(jù)挖掘的方式進(jìn)行信息的篩選、分析可以很好的解決傳統(tǒng)數(shù)據(jù)挖掘的不足?；谏鲜?，圖數(shù)據(jù)挖掘應(yīng)用到社交網(wǎng)絡(luò)可以很好的發(fā)揮數(shù)據(jù)挖掘的優(yōu)勢(shì)。
3.2圖數(shù)據(jù)挖掘在社交網(wǎng)絡(luò)的研究方法
社交網(wǎng)絡(luò)這個(gè)大的數(shù)據(jù)圖，在進(jìn)行圖數(shù)據(jù)挖掘時(shí)，可以把圖數(shù)據(jù)挖掘的挖掘方法應(yīng)用到社交網(wǎng)絡(luò)中。在進(jìn)行數(shù)據(jù)挖掘時(shí)，使用的算法可以完全使用圖數(shù)據(jù)挖掘的全部算法，這個(gè)結(jié)合實(shí)現(xiàn)過程如下所示：
（1）獲取社交網(wǎng)絡(luò)數(shù)據(jù)集。（2）社交網(wǎng)絡(luò)數(shù)據(jù)的預(yù)處理（數(shù)據(jù)清理、數(shù)據(jù)集成和變化、數(shù)據(jù)規(guī)約）。（3）特征的選取。（4）選擇合適的圖數(shù)據(jù)挖掘算法。（5）實(shí)時(shí)圖數(shù)據(jù)挖掘。（6）解釋和評(píng)估挖掘結(jié)果。（7）使用所發(fā)現(xiàn)的規(guī)則和模式。
在社交網(wǎng)絡(luò)應(yīng)用中，不同的應(yīng)用場(chǎng)景，圖數(shù)據(jù)挖掘有不同的應(yīng)用模式。Aggarwal介紹了社交網(wǎng)絡(luò)中網(wǎng)絡(luò)建模等存在的問題[29]，R.Soussi[30]等從社交網(wǎng)絡(luò)數(shù)據(jù)量的增長(zhǎng)性和數(shù)量型提出從圖形數(shù)據(jù)庫中抽取社交網(wǎng)絡(luò)關(guān)系的方法。對(duì)于圖數(shù)據(jù)挖的預(yù)測(cè)和Apriori和F-Tree算法在圖數(shù)據(jù)挖掘的效果方面S.Kadge[31]提出了基于圖預(yù)測(cè)社交網(wǎng)站。同樣的，J.Cao[32]等提出了構(gòu)建用戶交互模型，從而來預(yù)測(cè)不同用戶體和不同用戶群之間的交互情況。
4 結(jié)語
在當(dāng)今的社交網(wǎng)絡(luò)中，隨著數(shù)據(jù)結(jié)果的復(fù)雜性越來越明顯，圖數(shù)據(jù)挖掘在處理這些具有結(jié)構(gòu)化的數(shù)據(jù)結(jié)構(gòu)性數(shù)據(jù)的時(shí)候，對(duì)于圖數(shù)據(jù)挖掘提出了新的要求，對(duì)于新的關(guān)系、新的數(shù)據(jù)類型，圖數(shù)據(jù)挖掘需要采用相應(yīng)的處理模型和計(jì)算框架才能很好的解決不同的數(shù)據(jù)帶來的挑戰(zhàn)。文中綜述了圖數(shù)據(jù)挖掘的理論知識(shí)和相應(yīng)地應(yīng)用狀況，結(jié)合社交網(wǎng)絡(luò)的具體應(yīng)用場(chǎng)景，提出了相應(yīng)處理方式。相信隨著社交網(wǎng)絡(luò)數(shù)據(jù)的復(fù)雜性的改變和數(shù)據(jù)規(guī)模的不斷壯大，圖數(shù)據(jù)挖掘的發(fā)展會(huì)有相應(yīng)新的研究方法和研究熱點(diǎn)把圖數(shù)據(jù)挖掘做的越來越好。
參考文獻(xiàn)
[1]董西成.Hadoop技術(shù)內(nèi)幕:深入解析MapReduce架構(gòu)設(shè)計(jì)與實(shí)現(xiàn)原理[M].北京:機(jī)械工業(yè)出版社,2014:34-36.
[2]Malewicz G,Austern M H,Bik A J C,et al.Pregel:a system for large-scale graph processing[C].Proceedings of the 2010 ACM SIGMOD International Conference on Management of data.ACM,2010:135-146.
[3]Twister主頁[EB/OL].http://www.iterativemapreduce.org/.
[4]Haloop主頁[EB/OL].http://code.google.com/p/haloop/.
[5]于戈,谷峪,鮑玉斌,王志剛.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)[J].計(jì)算機(jī)學(xué)報(bào),2011,4(10):1753-1767.
[6]Malewicz G,Austern M H,Bik A J C,et al.Pregel:a system for large-scale graph processing[C].Proceedings of the 2010 ACM SIGMOD International Conference on Management of data.ACM,2010:135-146.
[7]Seo S,Yoon E J,Kim J,et al.Hama:An efficient matrix computation with the mapreduce framework[C].Cloud Computing Technology and Science(CloudCom),2010 IEEE Second International Conference on.IEEE,2010:721-726.
[8]KAMALAKANNAN M.Elevating a Data Warehousing and Analyzing System for e-meeting sites using cloud with Hama as deck[J].International Journal of Research in Information Technology and Sciences-IJRITS,2012,1(1).
[9]張海園.HAMA計(jì)算平臺(tái)的性能研究[D].北京:北京交通大學(xué),2012.
[10]Bin Shao,Haixun Wang,Yatao Li.Trinity:A Distributed Graph Engine on a Memory Cloud[EB/OL].http://research.microsoft.com/ apps/pubs/.
[11]周薇.海量圖數(shù)據(jù)的存儲(chǔ)與處理技術(shù)研究[D].北京:中國(guó)科學(xué)院大學(xué)碩士論文,2012.
[12]Neo4j介紹[EB/OL].http://www.neo4j.org/.
[13]Vicknair C,Macias M,Zhao Z,et al.A comparison of a graph database and a relational database:a data provenance perspective[C].Proceedings of the 48th annual Southeast regional conference.ACM,2010:42.
[14]HyperGraphDB簡(jiǎn)介[EB/OL].http://www.open-open.com/ open316576.htm.
[15]R.Giugno,D.Shasha.GraphgreP:AFastandUniversaIMethodforQ ueryingGraPhs[C].ICDE,2002:112-115.
[16]X.Yan,P.S.Yu,J.Han.GraphIndexing:aFrequentStrUeturebasedAPProaeh[C].SIGMOD,2004:335-346.
[17]S.Zhang,M.Hu,J.Yang.TreePi:ANovelGraPhIndexingMethod[C]. ICDE,2007:966-975.
[18]P.Zhao,J.X.Yu,P.S.Yu.GraphIndexing:Tree+Delta>=Graph[C]. VLDB,2007:938-949.
[19]R.Agrawal,A.Borgida,H.V.Jagadish.EffieientManageme ntofTransitiveRelationshiPsinLargeDataandKllowledgeBases[C]. SIGMOD,1989:253-262.
[20]S.Tripl,U.Leser.FastandPractiealIndexingandQueryingofVeryLar geGraPhs[C].SIGMOD,2007:845-856.
[21]徐賀賀.圖聚類算法機(jī)器在社交網(wǎng)絡(luò)中的應(yīng)用[D].合肥:安徽工程大學(xué),2013.
[22]L.Kaufan,PJ.Rousseeuw.Finding Groups in Data:an Introduction to Cluster AnaIysis[J].NewYork:JohnWiley&Sons,1990.
[23]Deshpande M,Kuramochi M,Karypis G.Frequent substructure based approaches for classifying chemical compounds IEEE Trans on Knowledge and Data Engineering,2005,17(8):1036-1050.
[24]Horvath T,Gartner T,Wrobel S.Cyclic pattern kernels for predictive graph mining[C]//Proceeding of the10th ACM SIGKDD Interational Conference on Knowledge Discovery and Data Mining. Washington DC,USA:ACM,2004:158-167
[25]Kashima H,Tsuda K,Inokuchi A.Marginalized kernels between labeled graphs[C]//Proceedings of the 20th International Conference on Machine Learning.WashingtonDC,USA:ICML,2003.
[26]Brogwardt K M,Kriegel H P.Shortest-path kernels on graphs[C]//Proceedings of the 5th IEEE Interational Conference on Data Mining(ICDM).Houston,Texas,USA:IEEE Computer Society,2005:74-81.
[27]尹婷婷,劉俊焱,周溜溜,葉寧,尹佟明.基于動(dòng)態(tài)抽樣的圖分類算法[J].南京師大學(xué)報(bào),2015,38(1):113-114.
[28]張偉.頻繁子圖挖掘算法的研究[D].秦皇島:燕山大學(xué),2011.
[29]Aggarwal C,Wang H X.Managing and mining graph data[M]. Berlin:Springer-Verlag,2010.
[30]Soussi R,Aufaure M,Baazaoui H.Towards social network extraction using a graph database[C]//Proc of second international conference on adcances in databases,knowledge,and data application.[s.1.]:[s.n.],2010:28-34.
[31]Kadge S,Bhatia G.Graph based gorecasting for social networking site[C]//Proc of international conference on communication,information and computing technology.[s.1.]:[s.n.],2011.
[32]Cao Jin,Gao Hongyu,Li L E,et al.Enterprise social network analysis and modeling:a tale of two graphs[C]//Proce of ONFOCOM. Turinate:IEEE,2013:2382-2390.
閆朋（1990-），男，河南鄧州人，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘。
高建瓴，碩士研究生導(dǎo)師，研究方向?yàn)榇髷?shù)據(jù)、云計(jì)算。
Research on Application of graph data mining in social networks
Yan Peng1Jian-ling Gao2
（1.Gui Zhou University School of computer science and technology，Guiyang 550025，Guizhou，China；2.Gui Zhou University School of big data institute，Guiyang 550025，Guizhou，China）
Abstract：The complexity of the social network data test for data mining，for the complexity of the data where in a social network using targeted treatment method is particularly important.Graph according to the relationship between data，data mining can make good use of its natural advantages to develop and analyze this kind of complex data entity connected closely linked.In this paper，it according to the characteristics of chart data mining and the approach of data mining.First of all，introduces the figure of data mining techniques of definition，and calculation model and processing system in chart data mining；Then introduces the application of graph data mining，mainly include the figure related content of the database and graph data algorithm，etc.；Finally，the whole describe of briefly introduced the development of social network and graph data mining and social network of the different model of combination for process and the processing method.
Key words：Graph data mining algorithm；Graph database；MapReduce；Neo4J；Frequent pattern
作者簡(jiǎn)介：
基金項(xiàng)目：貴州省科學(xué)技術(shù)基金（黔科合J字[2015]2045號(hào)）。
