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

無效

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

1.一種尋找社會網絡中極大k-plex的方法，其特征在于：所述方法包括下列操作步驟：

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

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

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

2.根據權利要求1所述的一種尋找社會網絡中極大k-plex的方法，其特征在于：所述步驟(2)中所述的基本生長方法包括下列操作步驟：

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

(22)從所述的社會網絡G中，找到該待基本生長k-plex的基本生長有效生長點集合；如果該待基本生長k-plex的基本生長有效生長點集合為空集，則轉到步驟(24)，否則找到該待基本生長k-plex的一個基本生長有效生長點，把該基本生長有效生長點添加到所述的待基本生長k-plex中，得到該待基本生長k-plex的子k-plex，把該子k-plex作為新的待基本生長k-plex，轉到步驟(23)；所述的基本生長有效生長點是指社會網絡G中的一個節點，該節點是所述待基本生長k-plex的一個生長點，并且該節點不是當前待基本生長k-plex所在支路中所有節點的兄弟節點中被生長過的兄弟節點；所述的兄弟節點是指兩節點具有相同的直接父節點，并且同時為該直接父節點所在的k-plex生長分支的生長點；

(23)如果該待基本生長k-plex節點數小于2k-1，則轉到步驟(22)進行遞歸基本生長操作；否則該待基本生長k-plex即為所要的一個節點數為2k-1的k-plex，予以保存，然后轉到步驟(24)繼續尋找新的節點數為2k-1的k-plex；

(24)如果該待基本生長k-plex是步驟(21)中所獲得的基本生長k-plex核，則轉到步驟(21)；否則找到該待基本生長k-plex的最近父k-plex，如果該待基本生長k-plex的最近父k-plex的基本生長有效生長點集合中還有未生長過的節點，則取出其中任意節點，加入到該待基本生長k-plex的最近父k-plex中形成新的k-plex，并把這個新形成的k-plex作為新的待基本生長k-plex，轉到步驟(22)進行新分支的基本生長；如果該待基本生長k-plex的最近父k-plex的基本生長有效生長點集合中所有的節點都已經生長過，則把該待基本生長k-plex的最近父k-plex作為新的待基本生長k-plex，轉到步驟(24)。

3.根據權利要求1所述的一種尋找社會網絡中極大k-plex的方法，其特征在于：所述步驟(3)中所述的有序生長方法包括下列操作步驟：

(31)把步驟(2)中所獲得的節點數為2k-1的k-plex集合作為有序生長k-plex核的集合，從中拿出一個k-plex，作為待有序生長k-plex，轉到步驟(32)進行有序生長；如果步驟(2)中所獲得的節點數為2k-1的k-plex集合已經變為空集，則所述步驟(3)的操作全部結束；

(32)找到該待有序生長k-plex的生長點集合和有序生長有效生長點集合；所述的有序生長有效生長點是指社會網絡G中的一個節點，該節點是所述的待有序生長k-plex的一個生長點，并且該節點的編號小于所述的該待有序生長k-plex所構成的生長分支中所有節點的編號；

(33)如果該待有序生長k-plex的有序生長有效生長點集合為空集，并且如果該待有序生長k-plex的生長點集合同時為空集，則該待有序生長k-plex的有序生長操作結束，該待有序生長k-plex所構成的生長分支即為所尋找到的所述的社會網絡G的一個極大k-plex，予以保存；然后轉到步驟(34)；

如果該待有序生長k-plex的有序生長有效生長點集合為空集，并且如果該待有序生長k-plex的生長點集合不為空集，則轉到步驟(34)；

如果該待有序生長k-plex的有序生長有效生長點集合不為空集，并且如果該待有序生長k-plex的有序生長有效生長點集合的所有節點與該待有序生長k-plex中的最新節點，已經同時全部包含于該待有序生長k-plex的父k-plex的某個生長分支之中，則轉到步驟(34)；否則從該待有序生長k-plex的有序生長有效生長點集合中找到那個編號最大的節點，把該節點添加到所述的待有序生長k-plex中，得到該待有序生長k-plex的最近子k-plex，并把該最近子k-plex作為新的待有序生長k-plex，轉到步驟(32)進行遞歸有序生長；

(34)如果該待有序生長k-plex是步驟(2)中所獲得的有序生長k-plex核，則轉到步驟(31)；否則找到該待有序生長k-plex的最近父k-plex，如果該待有序生長k-plex的最近父k-plex的有序生長有效生長點集合中還有未生長過的節點，則取出其中編號最大的節點，加入到該待有序生長k-plex的最近父k-plex中形成新的k-plex，并把這個新生成的k-plex作為新的待有序生長k-plex，轉到步驟(32)進行新分支的有序生長；如果該待有序生長k-plex的最近父k-plex的有序生長有效生長點集合中所有的節點都已經生長過，則把該待有序生長k-plex的最近父k-plex作為新的待有序生長k-plex，轉到步驟(34)。