[發明專利]一種基于局部相似度的社區挖掘方法

有效

• 申請號: 201410167205.9
• 申請日: 2014-04-24
• 公開（公告）號: CN103927371B
• 公開（公告）日: 2017-02-22
• 發明（設計）人: 翁偉;朱順痣;曾志強;張念;肖蕾;馬櫻
• 申請（專利權）人: 廈門理工學院
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京科億知識產權代理事務所(普通合伙)11350
• 代理人: 湯東鳳

技術領域

本發明涉及一種社區挖掘方法，具體地說，具體涉及一種基于局部相似度的社區挖掘方法。

背景技術

社會網絡是由一些個人或組織以及它們之間的聯系所構成的集合。20世紀90年代，隨著網絡技術的迅猛發展，特別是近幾年SNS(socialnetworkingsystem)的涌現，越來越多的個人用戶加入到由這些虛擬關系所構建的網絡中，社會網絡的研究得到了逐步加強。現今涌現出了大量的社會網絡平臺，包括網絡論壇(如天涯社區,CSDN，小蟲網等)，聊天室(如新浪聊天室)，校園BBS系統(如水木清華，一塌糊涂等)，社會關系網站(如Facebook等)，博客(如Myspace，Twitter)，即時通訊網絡(如MSN、QQ)等等，積累了海量的、不斷更新的社會網絡數據。這些社會網絡是人們現實生活直接或間接的反應，并進一步影響了人們的社會行為，例如網站中互相評論、標記和連接日志的博友是現實生活中的好友，或者可能發展為現實生活中的好友，維基百科(Wikipedia)已經成為互聯網上最大、最流行的參考書，IMDB論壇上的影片評論成為觀眾購票觀影的指南。

社區是復雜的社會網絡的基本特征之一。將社會網絡抽象成圖，將參與的對象表示成點，對象之間的關系表示成線，則社區為一個子圖，該子圖內部的關系比較緊密，子圖與子圖外部(其他子圖)之間的關系相對稀疏。物理類聚，人以群分，認識網絡中的社區結構，有助于理解復雜的網絡結構中組織架構，進而能夠理解對象之間關系的相互影響和組織功能。目前社區挖掘方法往往從某些角度定義一個描述社區優劣的定量指標，然后利用貪心算法，將初始網絡看成一個社區不斷拆分或將初始網絡中每個結點看成是一個社區不斷合并，最終使得這個指標盡可能達到最優。也有一些方法需要預定義參數(比如社區個數等閾值)和某種關系度量函數對網絡結點進行分類得出社區結構?？偠灾@些方法事實上限制了社區形成的過程、形狀和結構。

發明內容

為了克服現有技術中存在的缺陷，本發明提供一種基于局部相似度的社區挖掘方法，該方法通過網絡結構本身聯系的緊密與否發現關系緊密的局部區域，將這些局部區域視為社區的雛形賦予初始標簽，然后根據投票原則采用標簽傳播的辦法再擴展、調整這個區域形成社區。不需要任何人工參數，直接通過網絡本身結點聯系的緊密與否的結構性質得到社區結構。

為了敘述方便，先對基本概念進行形式化定義。設網絡G＝(V,E)，其中V＝{v₁,v₂,......v_n}為結點集合，E＝{e₁,e₂,......e_m}為邊集，其中e_i∈V×V。v_i的鄰居記為N(v_i)，即N(v_i)＝{v_j|w_ij＞0}，v_i的星型鄰域St(v_i)＝{v_i}∪N(v_i)。記表示結點v_i關聯的邊權值之和，定義為v_i的度。

其技術方案如下：

一種基于局部相似度的社區挖掘方法，包括以下步驟：

(1)根據網絡的鄰接矩陣計算各結點對的相似度。

那么結點對(v_i,v_j)的相似度計算公式如下：