[發(fā)明專(zhuān)利]一種網(wǎng)絡(luò)特征社區(qū)查找方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010075210.2
• 申請(qǐng)日: 2020-01-22
• 公開(kāi)（公告）號(hào): CN111274498B
• 公開(kāi)（公告）日: 2023-06-23
• 發(fā)明（設(shè)計(jì)）人: 王宏志;王春楠;陳含笑
• 申請(qǐng)（專(zhuān)利權(quán)）人: 哈爾濱工業(yè)大學(xué)
• 主分類(lèi)號(hào): G06F16/9536
• 分類(lèi)號(hào): G06F16/9536;G06Q50/00
• 代理公司: 哈爾濱市松花江專(zhuān)利商標(biāo)事務(wù)所 23109
• 代理人: 張利明

一種網(wǎng)絡(luò)特征社區(qū)查找方法，屬于網(wǎng)絡(luò)社區(qū)構(gòu)建技術(shù)領(lǐng)域。解決了現(xiàn)有升級(jí)版的社區(qū)搜索和特征社區(qū)查找存在的效率低且適應(yīng)性差的問(wèn)題。本發(fā)明根據(jù)真實(shí)的社區(qū)的內(nèi)部結(jié)構(gòu)特征和外部結(jié)構(gòu)特征，建立社區(qū)節(jié)點(diǎn)的內(nèi)部連結(jié)密度評(píng)估函數(shù)；建立社區(qū)節(jié)點(diǎn)的外部連結(jié)密度評(píng)估函數(shù)；對(duì)待搜索的網(wǎng)絡(luò)社區(qū)的屬性和給定屬性之間的相關(guān)度進(jìn)行量化，建立網(wǎng)絡(luò)社區(qū)的屬性相關(guān)性評(píng)估函數(shù)；對(duì)社區(qū)節(jié)點(diǎn)的內(nèi)部連結(jié)密度評(píng)估函數(shù)、社區(qū)節(jié)點(diǎn)的外部連結(jié)密度評(píng)估函數(shù)和量化的待搜索的網(wǎng)絡(luò)社區(qū)的屬性和給定屬性相關(guān)度的函數(shù)進(jìn)行融合，獲取函數(shù)RACSF；利用NSS節(jié)點(diǎn)選擇策略和彈性ISC循環(huán)終止條件對(duì)函數(shù)RACSF進(jìn)行優(yōu)化，獲取目標(biāo)社區(qū)結(jié)構(gòu)的最優(yōu)解為最終查找的特征社區(qū)。本發(fā)明適用于網(wǎng)絡(luò)特征的查找使用。

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

本發(fā)明屬于網(wǎng)絡(luò)社區(qū)構(gòu)建技術(shù)領(lǐng)域。

背景技術(shù)

在網(wǎng)絡(luò)相關(guān)研究工作中，社區(qū)(community)的概念持續(xù)受到人們的關(guān)注。由大量節(jié)點(diǎn)和節(jié)點(diǎn)間的連接關(guān)系構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)廣泛存在于計(jì)算機(jī)科學(xué)、生物學(xué)和社會(huì)學(xué)等領(lǐng)域，例如以網(wǎng)頁(yè)為節(jié)點(diǎn)、以網(wǎng)頁(yè)間的鏈接為邊組成的萬(wàn)維網(wǎng)和以人為節(jié)點(diǎn)、以人際間關(guān)系為邊建立的社會(huì)網(wǎng)等。一般而言，社區(qū)是指內(nèi)部節(jié)點(diǎn)間聯(lián)系較內(nèi)部與外部節(jié)點(diǎn)間聯(lián)系更為緊密的子網(wǎng)絡(luò)，發(fā)現(xiàn)網(wǎng)絡(luò)中的各種社區(qū)結(jié)構(gòu)(如社區(qū)發(fā)現(xiàn)和社區(qū)搜索)有助于進(jìn)行好友推薦、犯罪團(tuán)伙識(shí)別以及蛋白質(zhì)功能預(yù)測(cè)，同時(shí)能夠有效支持網(wǎng)絡(luò)中傳播熱點(diǎn)選擇和介數(shù)中心度更新。

不同于社區(qū)發(fā)現(xiàn)(community?detection)，社區(qū)搜索(community?search)旨在尋找包含給定節(jié)點(diǎn)集的社區(qū)，能夠快速獲取個(gè)性化的社區(qū)信息，即給定一個(gè)或多個(gè)節(jié)點(diǎn)，尋找包含它們的社區(qū)。但是真實(shí)世界的各類(lèi)網(wǎng)絡(luò)結(jié)構(gòu)中每一個(gè)節(jié)點(diǎn)并非毫無(wú)意義，它們也存在相關(guān)特征屬性，如Facebook社交網(wǎng)絡(luò)中，以每一個(gè)用戶為節(jié)點(diǎn)，以人際關(guān)系為邊構(gòu)建的社交網(wǎng)絡(luò)中，每個(gè)用戶個(gè)體都有各自不同的興趣愛(ài)好，這意味著網(wǎng)絡(luò)圖中每個(gè)節(jié)點(diǎn)都具有特征，而如何找到包含給定節(jié)點(diǎn)集且具有高度特征相關(guān)性的社區(qū)即又引出社區(qū)搜索的一個(gè)新的研究方向——特征社區(qū)查找。此相關(guān)研究具有極大的社會(huì)應(yīng)用價(jià)值，如組織科學(xué)研討會(huì)等社交活動(dòng)，調(diào)整產(chǎn)品廣告投放等市場(chǎng)決策，以及社交平臺(tái)好友推薦等。

現(xiàn)有的社區(qū)搜索方法包括僅與網(wǎng)絡(luò)拓?fù)溆嘘P(guān)的社區(qū)搜索和與節(jié)點(diǎn)屬性有關(guān)的社區(qū)搜索：前者旨在尋找包含給定節(jié)點(diǎn)集且滿足k-clique，k-core或k-truss等特定拓?fù)浣Y(jié)構(gòu)的社區(qū)；后者在查找包含給定節(jié)點(diǎn)集的社區(qū)時(shí)綜合考慮了拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性，返回的結(jié)果社區(qū)不僅要滿足特定拓?fù)浣Y(jié)構(gòu)，還要使內(nèi)部節(jié)點(diǎn)的屬性盡可能相近。而針對(duì)節(jié)點(diǎn)屬性相關(guān)的社區(qū)搜索，即特征社區(qū)查找問(wèn)題，目前提出的方法有ACC(Attributed?Community?CL-tree?index?Method.特征社區(qū)CL樹(shù)索引方法)和LocATC((Attributed?truss?index-basedquery?processing?algorithm?by?means?of?local?exploration.基于局部探究的基于屬性桁架索引的查詢(xún)處理算法)，它們?cè)趯?shí)際的圖網(wǎng)絡(luò)中也取得了良好的搜索結(jié)果。

由先前的研究可知，社區(qū)搜索是社區(qū)發(fā)現(xiàn)問(wèn)題在不同角度下的拓展；一般而言，社區(qū)發(fā)現(xiàn)旨在發(fā)現(xiàn)一張圖中的所有社區(qū)結(jié)構(gòu)，沒(méi)有其他限定要求。目前已提出的社區(qū)發(fā)現(xiàn)模型有譜聚類(lèi)模型，標(biāo)簽傳播模型，局部擴(kuò)展模型等，但它們并不是基于詢(xún)問(wèn)而查找社區(qū)，因此其最顯著的缺陷是不適用于快速在線的社區(qū)搜索，且在大型圖網(wǎng)絡(luò)中發(fā)現(xiàn)社區(qū)會(huì)耗費(fèi)大量時(shí)間。此外，現(xiàn)有的社區(qū)搜索算法也只能尋找包含給定節(jié)點(diǎn)集且滿足k-clique，k-core或k-truss等特定拓?fù)浣Y(jié)構(gòu)的社區(qū)，而且這些算法對(duì)于與節(jié)點(diǎn)屬性相關(guān)的特征圖關(guān)注甚少，因而在搜索中忽略了大量有助于社區(qū)搜索的節(jié)點(diǎn)屬性信息。