《異質網路中的社區發現》是依託武漢理工大學，由劉欣擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：異質網路中的社區發現
- 項目類別：青年科學基金項目
- 項目負責人：劉欣
- 依託單位：武漢理工大學
項目摘要,結題摘要,
項目摘要
根據給定網路的連線結構，將節點劃分為若干組，使得各組節點分別對應於某一功能單元，以上過程稱為社區發現。近年來，社區發現受到很多學者的關注，他們往往將此問題限定於同質網路。現實中，由不同類節點和邊構成的異質網路以多種形式廣泛存在，而同質網路的社區發現算法無法適用於更為複雜的異質網路。本項目在同質網路的最最佳化、資訊理論、譜分析、統計推斷等理論的擴展和延伸的基礎上，引入分而治之、整體規劃、等價轉化和函式最佳化四個思路來建立算法框架，對形形色色異質網路中的社區發現展開系統的研究，以揭示異質網路結構和功能之間的關係，為現實複雜異質系統的結構分析、未知功能探測和知識發現提供有效的方法和途徑。本課題的預期研究成果在Web信息搜尋、網站用戶行為分析、定向廣告、個性化服務等方面具有廣泛的套用前景。
結題摘要
根據給定網路的連線結構，將節點劃分為若干組，使得各組節點分別對應於某一功能單元，以上過程稱為社區發現。近年來，社區發現受到很多學者的關注，他們往往將此問題限定於同質網路。現實中，由不同類節點和邊構成的異質網路（heterogeneous network）以多種形式廣泛存在，比如在社會關係網路中有表示友誼、敵對和商業等關係的不同類型的邊。又比如在照片服務網站Flickr中，“用戶”可以上傳“照片”，對“照片”用“標籤”加以評註，加其它“用戶”為好友。那么，Flickr系統可以被描述成一個異質網路，其中包含“用戶”、“照片”、“標籤”三類節點和分別表示以上三種行為的三類邊。此外，除了節點和邊的拓撲信息外，現實世界中很多網路常常附帶節點和邊的屬性信息，比如社會網路的節點有年齡、愛好、國籍、宗教信仰、住所等屬性信息，邊有距離、親密程度等屬性信息。我們稱這些網路為屬性網路（attributed network）。傳統的同質網路的社區發現算法無法適用於更為複雜的異質網路和屬性網路。我們對這一問題分別採用分而治之、整體規劃、等價轉化和函式最佳化四個思路進行研究，提出了三個算法框架。我們對算法進行了廣泛測試，分別將它們套用於人工網路，被世界學者普遍使用的小規模網路，法國Orange公司提供的現實手機通訊網路，以及人工採樣得到的Digg大規模網路，揭示出網路結構和功能之間的關係，實現了系統的可視化，並總結出不同算法的優缺點和適用範圍。其中，基於分而治之的算法具有速度快，並行性好等特點，適用於節點和邊的類別相對較少的異質網路；基於整體規劃的算法具有準確性高的特點，適用於噪音較多，社區對應關係複雜的異質網路；基於函式最佳化的算法是對傳統模組度算法的一個歸納升華，既能套用到傳統的非屬性網路中挖掘層次社區結構，也能套用於屬性網路中挖掘屬性無關的社區。我們的研究為現實複雜系統的結構分析、未知功能探測和知識發現提供了有效的方法和途徑。
