加權圖中Closeness Centrality前k高之估算方法;Estimating Nodes of Top-k Closeness Centrality in Edge-Weighted Graphs

National Chung Cheng University Institutional Repository > 工學院 > 資訊工程學系 > 學位論文 > Item A095B0000Q/23

Please use this identifier to cite or link to this item: http://ccur.lib.ccu.edu.tw/handle/A095B0000Q/23

Title:	加權圖中Closeness Centrality前k高之估算方法;Estimating Nodes of Top-k Closeness Centrality in Edge-Weighted Graphs
Authors:	李建恆;Lee, Hendry
Contributors:	資訊工程研究所
Keywords:	社群網路;緊密度中心性;social network;closeness centrality
Date:	2018
Issue Date:	2019-05-23 10:30:11 (UTC+8)
Publisher:	資訊工程研究所
Abstract:	近幾年來，在各種網路圖上作centrality的分析是討論度極高的議題，因為centrality的數據能在各種應用中都能提供相當的幫助。而在一些centrality(例如:betweenness及closeness)的計算中都是基於最短路徑的計算，但由於現今的網路圖(尤其是社群網路的圖)的資料量都相當龐大，為了計算centrality的最短路徑計算就會變成一個相當耗時的工程，所以在很多研究中都在修改最短路徑演算法，以此希望能大幅度減少前置的最短路徑計算時間，且同時在估算前k個centrality較高的點是哪些時，又可以得到相當不錯的命中率，而大部分的研究都著重在無權重的圖上做分析，在本文中將提供一些修改的方法使得原本在無權重圖才能用到的修改方法可以使用在有權重的圖上，又能得到不錯的結果，且本文的研究將會著重在closeness centrality上。 Social network analysis is a hot issue in recent years. Centralities are usedto represent the importances of nodes. By definition, the closeness centralityinvolves computing the total distance to all other nodes and is therefore verytime-consuming. In this study, we focus on estimating node of top-k closenesswithout computing all-to-all distances. For each node, instead of computingthe shortest paths to all other nodes, we define the "local closeness" whichinvolves the number of nodes and their distance within a specified radius, andwe use the local closeness to estimate the nodes of top-k closeness.
Appears in Collections:	[資訊工程學系] 學位論文

Files in This Item:

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

Loading...