[發明專利]一種社交網絡子結構計數的方法

在審

• 申請號: 202110326703.3
• 申請日: 2021-03-26
• 公開（公告）號: CN113065099A
• 公開（公告）日: 2021-07-02
• 發明（設計）人: 龔世才;蘇常保;張莉萍
• 申請（專利權）人: 浙江科技學院
• 主分類號: G06F17/18
• 分類號: G06F17/18;G06Q50/00
• 代理公司: 杭州萬合知識產權代理事務所(特殊普通合伙) 33294
• 代理人: 丁海華;萬珠明

1.一種社交網絡子結構計數的方法，其特征在于：包括以下步驟：

S1：將社交網絡抽象為一個由多個節點和鄰邊構成的社交網絡圖,再將社交網絡圖用二值鄰接矩陣來表示；

S2:建立子結構計數程序，子結構計數程序內置有多個子結構個數的計數算法；

S3:將二值鄰接矩陣作為子結構計數程序的輸入，利用子結構計數程序輸出子結構的個數。

2.根據權利要求1所述的社交網絡子結構計數的方法，其特征在于：所述步驟S1中，社交網絡圖為無屬性無方向的簡單圖，表示為G＝(V,E)；

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

3.根據權利要求2所述的社交網絡子結構計數的方法，其特征在于：所述的二值鄰接矩陣為A＝(a_ij)_n×n；

其中a_ij的值為0或者1，i和j表示頂點v_i和v_j的下標；

當v_i和v_j之間有邊關聯時：a_ij＝1；當v_i和v_j沒有邊關聯或者i和j相等時：a_ij＝0；n表示頂點的個數。

4.根據權利要求1所述的社交網絡子結構計數的方法，其特征在于：所述子結構包括k-匹配圖、含圈圖、星圖、路圖和具有一條懸掛邊的圖。

5.根據權利要求4所述的社交網絡子結構計數的方法，其特征在于：所述k-匹配圖表示在社交網絡中具有某種潛在特征的成對人群，包括2-匹配，3-匹配和4-匹配，分別對應的子結構名稱為2P₂，3P₂和4P₂；所述子結構2P₂，3P₂和4P₂的計數算法分別如下：

式中：m表示社交網絡圖的邊數，n表示社交網絡圖的頂點數；d_i表示圖上節點i的度，C表示組合數；||Aⁿ||表示鄰接矩陣A的n次方所有元素之和；tr(Aⁿ)表示鄰接矩陣A的n次方對角線元素之和，α(G)表示子結構S₄∩P₂的個數，S₄表示為中心節點度為4的圖；P₂表示路徑為2的圖。

6.根據權利要求4所述的社交網絡子結構計數的方法，其特征在于：所述含圈圖表示人物關系構成一種圈狀的社交關系圖，包括三角形，四邊形和五邊形，分別對應的子結構名稱為C₃，C₄和C₅；所述子結構C₃，C₄和C₅的計數算法分別如下：

式中：m表示社交網絡圖的邊數，n表示社交網絡圖的頂點數；d_i表示圖上節點i的度，C表示組合數；tr(Aⁿ)表示鄰接矩陣A的n次方對角線元素之和，q₄表示社交網絡圖的無符號拉普拉斯矩陣的特征多項式第五系數，l₄表示社交網絡圖拉普拉斯矩陣的特征多項式第五系數；a₅表示社交網絡圖的二值鄰接矩陣A的特征多項式第六系數。