[發(fā)明專利]一種社交網(wǎng)絡(luò)子結(jié)構(gòu)計(jì)數(shù)的方法

在審

• 申請?zhí)枺?/td>: 202110326703.3
• 申請日: 2021-03-26
• 公開（公告）號: CN113065099A
• 公開（公告）日: 2021-07-02
• 發(fā)明（設(shè)計(jì)）人: 龔世才;蘇常保;張莉萍
• 申請（專利權(quán)）人: 浙江科技學(xué)院
• 主分類號: G06F17/18
• 分類號: G06F17/18;G06Q50/00
• 代理公司: 杭州萬合知識產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 33294
• 代理人: 丁海華;萬珠明

本發(fā)明公開了一種社交網(wǎng)絡(luò)子結(jié)構(gòu)計(jì)數(shù)的方法，包括以下步驟：S1：將社交網(wǎng)絡(luò)抽象為一個(gè)由多個(gè)節(jié)點(diǎn)和鄰邊構(gòu)成的社交網(wǎng)絡(luò)圖,再將社交網(wǎng)絡(luò)圖用二值鄰接矩陣來表示；S2:建立子結(jié)構(gòu)計(jì)數(shù)程序，子結(jié)構(gòu)計(jì)數(shù)程序內(nèi)置有多個(gè)子結(jié)構(gòu)個(gè)數(shù)的計(jì)數(shù)算法；S3:將二值鄰接矩陣作為子結(jié)構(gòu)計(jì)數(shù)程序的輸入，利用子結(jié)構(gòu)計(jì)數(shù)程序輸出子結(jié)構(gòu)的個(gè)數(shù)。本發(fā)明具有計(jì)算復(fù)雜度低、速度快的優(yōu)點(diǎn)。

技術(shù)領(lǐng)域

本發(fā)明涉及圖論以及矩陣?yán)碚摷夹g(shù)領(lǐng)域，具體涉及一種社交網(wǎng)絡(luò)子結(jié)構(gòu)計(jì)數(shù)的方法。

背景技術(shù)

圖的子結(jié)構(gòu)計(jì)數(shù)問題是圖理論研究的一個(gè)重要課題，在自然科學(xué)，社會科學(xué)，人文科學(xué)等許多其他領(lǐng)域有著重要的應(yīng)用價(jià)值。典型的子結(jié)構(gòu)計(jì)數(shù)問題包括生成樹計(jì)數(shù)問題、支配數(shù)問題、k-匹配數(shù)問題。然而，對于一般圖而言，圖的子結(jié)構(gòu)計(jì)數(shù)問題是困難的，甚至是NP-難的，比如k-匹配數(shù)問題是NP-完全問題。因而，具有特定結(jié)構(gòu)性質(zhì)的子圖計(jì)數(shù)問題和具有特定性質(zhì)圖的子圖計(jì)數(shù)問題的研究具有非常重要的意義。例如當(dāng)我們研究一個(gè)社交網(wǎng)絡(luò)時(shí)，通常會研究在這個(gè)社會群體中，人與人之間的互動(dòng)關(guān)系，以及每個(gè)人在所屬的小群體中所扮演的主要角色和每個(gè)小群體的存在性，這些基本的關(guān)系通常決定著一個(gè)大的社交群體的屬性。但是如何查找具有特定關(guān)系的子結(jié)構(gòu)網(wǎng)絡(luò)成為研究者研究社交網(wǎng)絡(luò)的關(guān)鍵性問題。又例如，在社交網(wǎng)絡(luò)的脆弱性分析當(dāng)中，通常研究者會比較關(guān)注具有某個(gè)特定結(jié)構(gòu)的網(wǎng)絡(luò)的個(gè)數(shù)。比如星型結(jié)構(gòu)，這樣的結(jié)構(gòu)攻擊者通常比較感興趣，通過查找星型結(jié)構(gòu)的個(gè)數(shù)通常可以大概判斷出這個(gè)社交網(wǎng)絡(luò)的安全指數(shù)。因此如何簡便快捷對圖的子結(jié)構(gòu)計(jì)算成為了申請人亟待解決的技術(shù)問題。

發(fā)明內(nèi)容

本發(fā)明的目的在于，提供一種社交網(wǎng)絡(luò)子結(jié)構(gòu)計(jì)數(shù)的方法。本發(fā)明具有計(jì)算復(fù)雜度低、速度快的優(yōu)點(diǎn)。

為解決上述技術(shù)問題，本發(fā)明提供的技術(shù)方案如下：一種社交網(wǎng)絡(luò)子結(jié)構(gòu)計(jì)數(shù)的方法，包括以下步驟：

S1：將社交網(wǎng)絡(luò)抽象為一個(gè)由多個(gè)節(jié)點(diǎn)和鄰邊構(gòu)成的社交網(wǎng)絡(luò)圖,再將社交網(wǎng)絡(luò)圖用二值鄰接矩陣來表示；

S2:建立子結(jié)構(gòu)計(jì)數(shù)程序，子結(jié)構(gòu)計(jì)數(shù)程序內(nèi)置有多個(gè)子結(jié)構(gòu)個(gè)數(shù)的計(jì)數(shù)算法；

S3:將二值鄰接矩陣作為子結(jié)構(gòu)計(jì)數(shù)程序的輸入，利用子結(jié)構(gòu)計(jì)數(shù)程序輸出子結(jié)構(gòu)的個(gè)數(shù)。

上述的社交網(wǎng)絡(luò)子結(jié)構(gòu)技數(shù)的方法，其特征在于：所述步驟S1中，社交網(wǎng)絡(luò)圖為無屬性無方向的簡單圖，表示為G＝(V,E)；

其中V＝{v₁,v₂,v₃,...v_n}表示頂點(diǎn)集合；E＝{e₁,e₂,e₃,...e_m}表示邊的集合；e＝(v_i,v_j)表示頂點(diǎn)v_i和v_j有邊關(guān)聯(lián)。

前述的社交網(wǎng)絡(luò)子結(jié)構(gòu)計(jì)數(shù)的方法，所述的二值鄰接矩陣為A＝(a_ij)_n×n；

其中a_ij的值為0或者1，i和j表示頂點(diǎn)v_i和v_j的下標(biāo)；

當(dāng)v_i和v_j之間有邊關(guān)聯(lián)時(shí)：a_ij＝1；當(dāng)v_i和v_j沒有邊關(guān)聯(lián)或者i和j相等時(shí)：a_ij＝0；n表示頂點(diǎn)的個(gè)數(shù)。

前述的社交網(wǎng)絡(luò)子結(jié)構(gòu)計(jì)數(shù)的方法，所述子結(jié)構(gòu)包括k-匹配圖、含圈圖、星圖、路圖和具有一條懸掛邊的圖。