在有權重網路圖上的社群結構偵測研究;A Study on Community Structure Detecting on Weighted Networks

NCUIR > College of Electrical Engineering & Computer Science > Department of Computer Science and information Engineering > Research Project > Item 987654321/49658

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/49658

Title:	在有權重網路圖上的社群結構偵測研究;A Study on Community Structure Detecting on Weighted Networks
Authors:	何錦文
Contributors:	資訊工程系
Keywords:	有權重網路分析;偵測社群結構;研究領域：資訊工程--硬體工程
Date:	2011-08-01
Issue Date:	2012-01-17 19:07:00 (UTC+8)
Publisher:	行政院國家科學委員會
Abstract:	許多應用的問題都可以用圖論的問題來表示，例如：在社會學上的人際關係網路分析、在生物學上的蛋白質複合體偵測等。我們可以把原本問題中的運作物件視為圖形上的一個點，任意兩個物件若有關係存在時，則在圖形上用一條邊將他們連起來。在建構圖形並把原本問題轉成圖論上的問題後，則原本問題就從圖論角度來思考，並用圖論的技巧加以解決。在許多的真實世界的網路中，普遍存在社群結構；所謂的社群結構指的是在相同社群的節點其互動關係要比不同社群的節點來得較為頻繁。偵測社群是一個十分重要的題目，因為它的應用十分地廣泛。例如：偵測社群可以幫助我們在社會人際關係網路找出社會群體、在引用論文文獻所構成的網路中找出相同主題的論文、在蛋白質交互作用網中找出蛋白質複合體、在網際網路上找出相同話題的網頁。根據我們之前的研究發現，社群結構應由核心成員和附屬成員所構成，而核心成員應該是由網路中比較重要的節點所擔任，所以如果能更準確地找到網路中比較重要的節點，並配合適當的方法找出附屬成員，則可發展出更好的偵測社群結構之方法。過去我們在設計偵測社群方法時，重點放在處理沒有權重的網路，但由於近來我們發現一個適合在有權重的網路上找重要點的方法，經由初步的實驗，有相當不錯的結果。因此我們認為，若能利用這個新的找重要點的方法，應可發展出適用於有權重網路的偵測社群結構方法，此即我們這計畫的主要目標。 Many problems can be represented as graph theoretical problems, such as human relationship network analysis in social studies, and detecting protein complexes in Protein-Protein Interaction networks in biological studies, etc. We can construct a graph by adding vertices to represent entities in the original problem and linking any two vertices with an edge if there is a relationship between these two entities. After we create the graph and transfer the original problem to a graph theoretical problem, this problem can be solved by graph theoretical skills. Community, in which vertices are joined tightly together, between which there are only looser edges, exists in many real network networks. Detecting community in a network is a very important research topic, because it has many practical applications. For example, detecting communities can help us find out real social groupings in a social network, related papers on a single topic in a citation network, protein complexes in Protein-Protein Interaction networks and web pages on related topics in the internet. The research of our previous results show that a community is composed of core members and attachment members. That means if we can find the core members of a community, and then we have a big chance to find the community. According to our research experiment on this topic, we believe that the core members of a community are important vertices of a graph. Our previous study focused on detecting the community on unweighted graphs. Recently, we find a promising method to extract important vertices from weighted graphs. Based on this method, we think we can develop a good community detecting method for weighted graphs, and this is the goal of this project. 研究期間：10008 ~ 10107
Relation:	財團法人國家實驗研究院科技政策研究與資訊中心
Appears in Collections:	[Department of Computer Science and information Engineering] Research Project

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	318	View/Open

社群 sharing

Loading...