[發明專利]一種尋找社會網絡中極大k-plex的方法

無效

• 申請號: 201110264988.9
• 申請日: 2011-09-08
• 公開（公告）號: CN102289516A
• 公開（公告）日: 2011-12-21
• 發明（設計）人: 廖建新;王晶;王純;李煒;張濤;沈奇威;周瑤;徐童;朱曉民;張磊;張樂劍;樊利民;程莉
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及一種尋找社會網絡中極大k-plex的方法，屬于計算機網絡技術領域，特別是屬于社會網絡并行計算技術領域。

背景技術

隨著因特網和移動通信的發展和普及，網絡用戶之間通過各種網絡活動，構成了關系復雜的社會網絡。社會網絡中存在著一種相當普遍的特性——社群結構，社群是網絡中相對密集的區域，其內部實體間存在著緊密的連接，而區域之間相互隔離或只有少許聯系橋接其間。網絡社群是我們了解網絡結構、網絡功能和增長機制的一個重要工具。在社會網絡中，社群結構往往對應著現實社會中的小團體，來自同一社群的成員之間往往有許多共同的特性，比如興趣，愛好，思想，個性等。這一概念也可以擴展到其他網絡中，比如BBS(Bulletin?Board?System，電子公告牌)中的同一社群的人員通常意味著出現在相同的版面，討論著同一公共話題。發現一個網絡中的社群結構是對這個網絡進行研究的常用方式，具有極大的研究價值和應用價值，例如，在現今流行的精準營銷當中，可以通過對用戶所屬社群特征的判斷來為用戶推送相應的個性化內容，參見圖1，如SNS(Social?Networking?Services，即社會性網絡服務)社區中根據共同好友數判斷用戶社群從而進行好友推薦，在線閱讀平臺根據用戶閱讀歷史記錄判斷用戶閱讀偏好所屬社群進行書籍推薦，手機廣告平臺根據用戶信息進行社群分類從而發送定制廣告等。

參見圖2，為研究網絡社群，人們把社會網絡抽象成一個圖，圖中的節點表示網絡用戶，網絡用戶之間的網絡聯系用節點之間的邊來表示，圖2即為圖1所示SNS所對應圖的示意圖。關于網絡社群結構的研究很多，但是如何定義網絡中的社群結構，目前還沒有一個公認的定義，k-plex(稱為k-派系)就是眾多網絡社群定義中的一種。社會網絡中，k-plex子圖就是滿足如下條件的節點集合：即該集合中每個節點都與最多除了k個節點之外的其他節點直接相連，k是一個自然數。極大k-plex子圖則是不被任何其他的k-plex子圖包含的k-plex子圖。對于網絡來說，一個網絡的極大k-plex子圖則可以看成這個網絡的一個極大社群，這個社群在網絡中不被其他社群所包含，擁有自己獨立的特征。

如上所說，極大k-plex子圖是社會網絡中具有重要價值的網絡派系，因此，人們對如何尋找極大k-plex子圖做了很多的研究，但隨著社會網絡規模的急劇膨脹，目前的研究成果對大規模數據量的并行處理效果很不好，不能實現快速尋找到社會網絡中的極大k-plex子圖的目標。因此如何充分利用并行計算環境，從大規模的社會網絡中快速尋找到極大k-plex子圖成為當前社會網絡應用中一個急需要解決的技術難題。

發明內容

有鑒于此，本發明的目的是發明一種能充分利用并行計算環境，實現快速尋找社會網絡中極大k-plex的方法。

為了達到上述目的，本發明提出了一種尋找社會網絡中極大k-plex的方法，所述方法包括下列操作步驟：

(1)對社會網絡G中所有的節點進行編號，每個節點對應一個唯一的號碼；

(2)利用基本生長方法，找到社會網絡G中所有頂點數目為2k-1的k-plex，其中k為預先設定的一個大于1的自然數；

(3)以步驟(2)所得到的頂點數目為2k-1的k-plex作為基礎，利用有序生長方法，找出社會網絡G中所有節點數目大于等于2k-1的極大k-plex。

所述步驟(2)中所述的基本生長方法包括下列操作步驟：

(21)從所述的社會網絡G中，如果能找到構成一個連通圖的三個節點并且該三個節點中至少有一個不在任何一個已經搜尋到的k-plex派系中，則這三個節點構成一個k-plex核，把該k-plex核作為一個待基本生長k-plex，轉到步驟(22)進行遞歸基本生長操作；否則步驟(2)的全部操作結束；