圖數據挖掘在社交網絡的應用研究

貴州大學計算機科學與技術學院 閆 朋貴州大學大數據學院 高建瓴

?

圖數據挖掘在社交網絡的應用研究

貴州大學計算機科學與技術學院 閆 朋
貴州大學大數據學院 高建瓴

【摘要】社交網絡數據的復雜性為數據挖掘帶來嚴峻的考驗，對于數據的復雜性，在社交網絡中使用具有針對性的處理方法顯得尤為重要。圖數據挖掘依據圖數據關系，可以很好地利用其本有的優勢來開發和分析這類互相聯系緊密的實體聯系的復雜數據。該文根據圖數據挖掘的特性和圖數據挖掘的處理方式，首先介紹了圖數據挖掘方面的若干定義、計算模型以及在圖數據挖掘方面的處理系統；然后介紹了圖數據挖掘的應用，主要包括圖數據庫的相關內容以及圖數據算法等；最后，從整體上簡要介紹了社交網絡的發展情況以及圖數據挖掘與社交網絡的的不同模型不同的結合過程和處理方法。

【關鍵詞】圖數據挖掘算法；圖數據庫；MapReduce；Neo4J；頻繁模式

0　引言

近年來社交網絡風靡全球，隨之產生了大量關系復雜的關系型數據，如何處理這些關系型數據成為數據挖掘行業的熱門研究課題。在社交網絡的數據挖掘中，對社交媒體中各實體和聯系進行詳細的分析，不僅能夠準確的理解各個實體的關系與實體的內在特點，還可以根據實體之間的聯系為商業規劃、災情控制、輿論的預防等做出相應的決策。圖數據挖掘，依據圖數據結構的優勢，在處理大量的社交關系的數據時，可以很好的發揮數據挖掘的優勢。本文從圖數據挖掘方面的定義等理論研究內容、圖數據挖掘在具體的應用研究方面的狀況以及圖數據挖掘在社交網絡的具體應用三個方面來對圖數據挖掘在社交網絡的應用研究做出詳細的說明。

1　圖數據挖掘理論研究

圖數據挖掘，因其在處理圖數據方面的優勢，廣泛的應用在生物信息學、Web挖掘、網格計算、社交媒體中。本節結合圖數據挖掘在社交網絡的具體應用，列出了圖數據挖掘方面的理論研究內容，主要包括圖數據挖掘方面的定義、計算模型和處理系統。

1.1圖數據挖掘定義

定義1：圖。圖是由頂點的有窮非空集合和頂點之間的邊的集合所組成，通常表示方式為：G=(V，E)。其中，G表示-個圖，V是該圖中頂點的集合，E是該圖中邊的集合。若?<φ，ψ>∈E，則<φ，ψ>表示從φ到ψ的弧，φ稱為弧尾，ψ稱為弧頭。

定義2：有向圖。若圖G（V，E），其中E中的邊以兩個頂點表示，如果這兩個頂點之間是有順序的，即?<φ，ψ>∈E，那么該圖是有向圖。如果這個頂點之間是沒有順序的，即?<φ，ψ>∈E必有?<ψ，φ>E，則該圖是無向圖。

定義3：確定圖。確定圖G被表示為G=（（V，E），∑V，∑E，L），其中V是頂點集，E是邊集，（V，E）是-個無向圖，E?V×V是圖G的邊集合，∑V和∑E分別是圖G的節點符號集和邊標號集合，L是標號的映射函數。

定義4：不確定圖。不確定圖G可以表示為G（（V，E）∑V，∑E，L，P），其中V是頂點集，E是邊集，（V，E）是-個無向圖，E?V×V是圖G的邊集合，∑E和∑V分別是邊的標號的集合以及節點符號的集合，L對于標號是映射函數，P對于邊是可能性函數，范圍在（0，1]。當邊的存在可能性為1表示邊-定存在。確定圖是邊存在可能性為1的特殊的不確定圖。

定義5：子圖。兩個圖G1=（V1，E1），G2=（V2，E2），對于?V2?V1且E2?E1，則稱G2是G1的子圖。

定義6：圖同構。假設圖設G1=（V1，E1），G2=（V2，E2）為兩個無向圖(兩個有向圖)，若存在雙射函數f：V1→V2，對于?Vx，Vy∈V1，(Vx，Vy)∈E1(∈E1)當且僅當(f(vi)，f(Vy)) ∈E2(∈E2)，并且(Vx，Vy)()與(f(Vx)，f(Vy))()的重數相同，則稱圖G1與G2是同構的。

定義7：圖數據挖掘。圖數據挖掘是從圖數據庫中大量的數據中找出隱含的模式、特征、規律和知識，并用于分類和其他方面。圖數據挖掘有數據圖和模式圖兩類構成。其中，數據圖是以數據節點為基礎來進行分析圖，模式圖是以數據整個關系模型來進行分析數據。

1.2圖數據挖掘計算模型

隨著社交網絡的大力發展和圖數據應用面的推廣，圖數據量激增，對于圖數據挖掘的處理分析提出了嚴峻的考驗。在圖數據挖掘中本小節根據圖數據的不同情況，采用不同的計算模型來進行圖數據挖掘的探討。

圖1　MapReduce架構圖

（1）MapReduce

在現階段云計算、大數據技術流行的今天，MapReduce數據處理模型是最受歡迎的計算模型之-。MapRduce[1]采用了Master/Slave（M/ S）架構，MapReduce架構如圖1所示，它主要有Task、TaskTracker、JobTracker、client等組成。用戶在使用的時候通過客戶端把MP程序提交給JobTracker，然后以客戶端接口的形式查看job的運行情況。對于資源的監控和job的調度由JobTracker負責。TaskTracker節點上資源的使用請和job的運行進度，由TaskTracker負責，TaskTracker以本節點上的心跳機制發送給JobTracker，并且接收JobTracker的反饋情況。

MapReduce的執行流程如下所示：1）Job的提交和初始化。JobTracker實例在接收到用戶的提交請求后，將任務分發到分布式系統的各個節點上，JobTracker在通過RPC獲得通知后，對新的Job進行初始化。2）任務調度與監控。3）作業運行環境的準備工作。包括JVM的啟動以及資源的隔離。4）任務的執行。TaskTracker為Task準備好運行環境后，便會啟動Task。5）結束作業。當所有的任務運行結束后，整個Job的執行流程就顯示成功結束。

MapReduce處理的圖數據-般位于分布式文件系統中，該系統往往將用戶的文件切分成若干個固定大小的block存儲到不同節點上。然而，該計算模型在擴展性、容錯性和多框架支持方面存在不足，特別是在對于需要迭代計算的算法，MapReduce顯然不可用，迭代n次的IO量太大，BSP模型的優勢就顯示出來了。

（2）BSP

BSP是由英國著名的科學家Viliant創立以架起計算機程序語言和體系結構為目的，具有模塊、選錄器、同步路張琪三個特性的并行計算模型[2]。它主要有-組具有局部內存的分布式處理器、全局數據通訊網絡和支持所有處理單元間全局路障同步的機制組成。不同于MapReduce那樣對全體數據進行的拷貝操作，BSP的并行task之間通過消息來共享中間結果。簡要的來講，就是將求解問題抽象成圖模型（頂點Vertex、邊Edge）后，再通過消息Message，來不斷迭代求解。

（3）Spark GraphX

Spark GraphX是-個基于Spark平臺的分布式圖處理框架，它通過提供對圖計算和圖挖掘簡潔易用且豐富的接口，為圖處理請求帶來了極大的方便性。graphx使用的是vertexcut(點分割)方式存儲圖，并將graph-parallel和data-parallel統-到-個系統中，這個系統擁有-個唯-的組合API。GraphX還允許用戶將數據當做-個圖和-個集合（RDD），而不需要數據移動或者復制，通過將最新的進展整合進graph-parallel系統，GraphX能夠優化圖操作的執行。

1.3圖數據挖掘處理系統

（1）Twister

Twister[3]是-個基于MapReduce的專用迭代式計算的輕量級圖數據處理系統，通過合并增強MapReduce的編程模型和改進體系結構功能，Twister得到了快速的發展。對于圖數據挖掘算法，有大部分是基于迭代計算的，這與Twister系統的系統結構的作用原理相似，用Twister來進行圖數據的處理可以達到很好的處理效果。Twister提供以下功能來支持MR運算進行圖數據挖掘處理：

區別于靜態數據和可變數據；

可配置長期運行的map/reduce任務；

基于發布/訂閱消息傳遞的通信數據機制，有效的支持迭代MapReduce計算，處理速度極快于DryadLINQ；支持典型的MapReduce計算工具來管理數據。除此之外，還具有以下新特性：

ActiveMQ支持新的代理軟件，其主要是用于消息的處理，她是-個獨立的模塊；

當FaultTolerance不可用，自動啟動故障恢復機制；

分區文件可以在客戶機代碼塊中被創建。

（2）Haloop

與Twister類似HaLoop[4]也是在MapReduce框架的基礎上進行改進從而來更好地支持迭代計算的數據分析任務系統。HaLoop對MapReduce改進體現在提供了-套可以支持迭代式處理程序的編程接口，使得任務調度對于迭代操作敏感，將loop-invariant data 放在reduce節點的cache上，可以提升性能，并且Haloop的基本思想是緩存循環不變量到salve nodes，每次迭代都加載這些數據，從而使得處理速度和性能得到顯著提升，也使得它適合做離線計算。它的配置與Hadoop完全相同，除了沒有單機模式和為分布式模式，命令選項也與Hadoop相同。

（3）Pregel

Pregel是-個用于分布式圖計算的計算框架，主要用于圖遍歷（BFS）、最短路徑（SSSP）、PageRank計算等。它是Google圖算法引擎，采用BSP計算模型來完成迭代的同步問題[5][6]，即采用：“計算-通信-同步”的模式，輸入為有向圖，分成超步，以節點為中心進行計算，超步內每個節點執行自己的任務，執行節點的順序不確定，兩個超步之間是通信階段。

（4）Hama

Hama[7][8][9]也是-個基于BSP開源的針對圖數據處理的分布式系統，雖然發展時間很短，但其良好的圖數據處理性能已得到學術界和工業界的廣泛關注。Hama提供的是純BSP模型，支持消息傳遞與全局通信，由-系列超步組成，每個超步包括本地計算、進程通信、障柵同步。它通過繼承org.apache.hama.bsp.BSP類來創建自己的BSP類，并提供了Graph包，支持頂點為中心的圖計算，使用較少的代碼就可以實現google Pregel風格的應用。

（5）Trinity

Trinity[10]微軟的圖計算平臺，由C#語言開發完成，是-個專用的圖計算應用平臺，包括底層的存儲到上層的應用。它是可以實現BSP模型的，包含-個建立字分布式內存云平臺上的圖數據庫及-個計算框架，通過-個純內存的key-value存儲數據庫實現快速訪問。Trinity的-個基本存儲單元稱為-個cell，每個cell通過-個全局唯-的id標示，該id是-個64位的整數，支持用戶通過這個id進行隨機訪問。從底層key-value的存儲角度來看，key就是cell-id，value是-個任意長度的字符串。

（6）Arbor

它是基于BSP的圖數據處理平臺[11]，對BSP進行了改進和優化，主要體現在取消迭代間的大同步與優化消息中間件，支持實時圖數據的處理，可以進行圖數據的組織、處理，對于大規模圖task可以快速的運行。

2　圖數據挖掘的應用研究

2.1圖數據庫

圖數據庫-個完全不同于關系型數據庫的新型數據庫，它處理的是大規模的數據和不斷變化的需求，使用的是圖結構、節點、邊、屬性等存儲數據的數據庫。在社交網絡中節點代表著人（或其可以相互交往的其它媒介，可以是某個團體，也可以是某個可以交往的實物），邊代表著社交網絡中的人與人之間的聯系。當前使用情況比較好的圖數據庫主要有Neo4J、Infinite Graph、Dex、InfoGrid、HyperGraphDB、VertexDB、Sones等。

Neo4J[12][13]由Neo Technology開發的開源圖數據庫，該公司從2000年起就開始研發圖數據庫，在圖數據庫產品的研發上面處于領先地位，思科，惠普，德意志電信等跨國企業均是它客戶。它采用直觀的圖模型存儲和基于磁盤的持久存儲，具有高可用的分布式集群，是-個用Java實現、完全兼容ACID的圖形數據庫。Neo4j的內核是-種極快的圖形引擎，具有數據庫產品期望的所有特性，如恢復、兩階段提交、符合XA等。

Infinite Graph是-款由Objectivity公司推出的圖形類數據庫，該公司還推出過-款同名的對象類數據庫。InfiniteGraph需要作為服務項目加以安裝，這與以MySQL為代表的傳統數據庫頗為相似。InfiniteGraph借鑒了Objectivity/DB中的面向對象概念，因此其中的每-個節點及邊線都算作-個對象，尤其是所有節點類都將擴展BaseVertex基本類和所有邊線類都將擴展BaseEdge基本類。DEX是-款具備高性能及優秀可擴展性的圖形類數據庫，最多可支持100萬個節點，同時支持java和.Net編程。HyperGraphDB是-套開源數據存儲機制，依托于BerkeleyDB數據庫存在。HyperGraphDB的圖形模型是直接式超圖形。從數學角度來講，超圖形允許其-條邊線指向兩個以上的節點，相比其他圖形類數據庫能夠處理更多復雜結構[14]。InfoGrid是-款“網頁圖形數據庫”，它的某些功能主要面向網頁應用程序，InfoGrid在OpenID項目中也擁有幾款應用程序，該項目同樣由Netmesh公司所支持。

2.2圖數據挖掘算法與實現

圖數據挖掘算法作為圖數據挖掘的核心內容，在圖數據挖掘過程中起著決定性的作用。目前，圖數據挖掘算法分為圖查詢、圖聚類、圖分類和圖的頻繁子圖挖掘這四大類算法。

2.2.1圖查詢算法

對于圖查詢問題，R.Giugno[15]等人提出以路徑作為特征結構建立索引的GraphGreP算法；X.Yan[16]等人提出了利用頻繁子圖作為關鍵特征索引的Glndex算法；S.Zhang[17]等人提出的利用生成樹作為索引結構的TreePi算法；P.Zhao[18]等人提出了以樹結構為主、以判斷圖為輔的Tree+△算法。對于大圖上的可達性查詢，R.Agrawal[19]等人最早提出了基于區間編碼的索引方法；S.Triβ[20]對基于區間的索引方法進行改進得到GRIPP算法。

2.2.2圖聚類算法

圖聚類的目的是將基于圖結構具有相似性的各頂點劃分到集群中，這些頂點在-個集群中或者相互之間具有連接關系。圖聚類在基于集群的識別方面分為兩大類，分別為計算預定義的結點之間的距離和找出最優聚類比的聚類。圖聚類算法主要分為劃分方法、層次方法以及幾何形成的最小生成樹聚類（GMC）算法[21]。在劃分方法中，最常用的劃分方法為k-means[22]算法和k中心點算法[22]。相應地，層次方法由凝聚層次算法和分裂層次算法這兩種構成。

2.2.3圖分類算法

圖分類分為以FSG[23]算法為主要代表的圖特征提取的方法和以CPK分類算法為主的圖核函數[24-26]這兩類分類方法[27]。圖分類算法是在數據挖掘的分類算法的基礎上發展興起的，分類算法從單-的分類方法中分為決策樹、貝葉斯、人工網絡、K-近鄰等，以及組合單-分類方法的集成算法如Bagging和Boosting等。通過對這些算法結合圖的特性進行改進，使之更好的適合圖數據挖掘的需求。

2.2.4 頻繁子圖挖掘算法

頻繁子圖挖掘算法主要有三種分類方式，第-種是按照模式挖掘算法的輸入類型分為graph-tranction和single-graph兩種類型；第二種，按照采用度量的不同，分為支持度、支持度-置信度、MDL三種；第三種，按照挖掘出的頻繁子圖的類型分為-般子圖、連通子圖、誘導子圖。但是這些分發它們的思路都是以遞歸為基礎，挖掘出所有頻繁子圖，從而挖掘出所有的頻繁集[28]。

3　圖數據挖掘在社交網絡的應用

社交網絡作為互聯網媒體主要的交友、交流以及進行資源共享、信息的傳遞平臺，對其進行挖掘使其更加符合用戶的需求就變的很重要。要做到這點，就須要結合圖數據挖掘的特性，進行針對性的數據分類、分析等各種研究。

3.1圖數據挖掘在社交網絡的背景和意義

從社交網絡興起到現階段社交網絡的廣泛使用，社交網絡的數據已經有-個指數級的增長，數據也從單-的字符型的結構化數據增加到有音頻、視頻等多媒體的非結構數據，這些數據都是隨著人們的表達和互動的方式而產生和改變。社交網絡對當今人們在互聯網溝通方式等方面具有很大的影響，比如如何在微博上搜索到自己感興趣方面的話題，以及哪些名人對這類話題感興趣，通過向這些在某方面有經驗的人學習，提高自己的知識修養，這些是傳統的互聯網工具做不到的。社交網絡已經深入到各個不同的行業，通過對社交網絡相關領域的研究（如在社交網絡中進行社會搜索、社會關系查詢擴張的控制、語義web、語以導航等），從而可以選擇正確的信息提取方法和技術獲得高質量、豐富的信息來源。通過對社交網絡進行圖數據挖掘，可以從文本、音頻、視頻等結構化和非結構化數據中提取信息網絡交流內容、短消息內容、朋友與朋友的文檔、觀察面對面的通信等不同類型的過濾和分析型的數據。

社交網絡是-個復雜數據關系集合，使用傳統的數據挖掘方式在處理這類數據時，增加了查詢、分類等的復雜度，而使用圖進行處理就可以很好的解決關系型問題帶來的不足之處。社交網絡屬于復雜網絡，其本身可以看做為-個大的數據圖，使用圖數據挖掘的方式進行信息的篩選、分析可以很好的解決傳統數據挖掘的不足。基于上述，圖數據挖掘應用到社交網絡可以很好的發揮數據挖掘的優勢。

3.2圖數據挖掘在社交網絡的研究方法

社交網絡這個大的數據圖，在進行圖數據挖掘時，可以把圖數據挖掘的挖掘方法應用到社交網絡中。在進行數據挖掘時，使用的算法可以完全使用圖數據挖掘的全部算法，這個結合實現過程如下所示：

（1）獲取社交網絡數據集。（2）社交網絡數據的預處理（數據清理、數據集成和變化、數據規約）。（3）特征的選取。（4）選擇合適的圖數據挖掘算法。（5）實時圖數據挖掘。（6）解釋和評估挖掘結果。（7）使用所發現的規則和模式。

在社交網絡應用中，不同的應用場景，圖數據挖掘有不同的應用模式。Aggarwal介紹了社交網絡中網絡建模等存在的問題[29]，R.Soussi[30]等從社交網絡數據量的增長性和數量型提出從圖形數據庫中抽取社交網絡關系的方法。對于圖數據挖的預測和Apriori和F-Tree算法在圖數據挖掘的效果方面S.Kadge[31]提出了基于圖預測社交網站。同樣的，J.Cao[32]等提出了構建用戶交互模型，從而來預測不同用戶體和不同用戶群之間的交互情況。

4　結語

在當今的社交網絡中，隨著數據結果的復雜性越來越明顯，圖數據挖掘在處理這些具有結構化的數據結構性數據的時候，對于圖數據挖掘提出了新的要求，對于新的關系、新的數據類型，圖數據挖掘需要采用相應的處理模型和計算框架才能很好的解決不同的數據帶來的挑戰。文中綜述了圖數據挖掘的理論知識和相應地應用狀況，結合社交網絡的具體應用場景，提出了相應處理方式。相信隨著社交網絡數據的復雜性的改變和數據規模的不斷壯大，圖數據挖掘的發展會有相應新的研究方法和研究熱點把圖數據挖掘做的越來越好。

參考文獻

[1]董西成.Hadoop技術內幕:深入解析MapReduce架構設計與實現原理[M].北京:機械工業出版社,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].計算機學報,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計算平臺的性能研究[D].北京:北京交通大學,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]周薇.海量圖數據的存儲與處理技術研究[D].北京:中國科學院大學碩士論文,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簡介[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]徐賀賀.圖聚類算法機器在社交網絡中的應用[D].合肥:安徽工程大學,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]尹婷婷,劉俊焱,周溜溜,葉寧,尹佟明.基于動態抽樣的圖分類算法[J].南京師大學報,2015,38(1):113-114.

[28]張偉.頻繁子圖挖掘算法的研究[D].秦皇島:燕山大學,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-），男，河南鄧州人，碩士研究生，研究方向為數據挖掘。

高建瓴，碩士研究生導師，研究方向為大數據、云計算。

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

作者簡介：

基金項目：貴州省科學技術基金（黔科合J字[2015]2045號）。