跳到主要內容

臺灣博碩士論文加值系統

(3.236.50.201) 您好!臺灣時間:2021/08/06 09:29
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳暐杰
研究生(外文):CHEN, WEI-JIE
論文名稱:一個有效率的方法去找到高中介度中心性的點
論文名稱(外文):An efficient method for finding vertices of high betweenness
指導教授:吳邦一
指導教授(外文):WU, BANG-YE
口試委員:江季翰吳邦一黃耀廷
口試委員(外文):JIANG,JI-HANWU, BANG-YEHUANG, YAO-TING
口試日期:2017-06-29
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2017
畢業學年度:105
語文別:英文
論文頁數:42
中文關鍵詞:中介度中心性社會網路
外文關鍵詞:betweenness centralitysocial network
相關次數:
  • 被引用被引用:0
  • 點閱點閱:133
  • 評分評分:
  • 下載下載:16
  • 收藏至我的研究室書目清單書目收藏:0
中心性是一種量化點在社會網路上的重要性的一種指標,一個點的中介度是它在最短路徑上的次數,然而,計算中介度中心性的計算量是非常龐大的。在許多實際應用中,我們並不是要求出一個點正確的中介度中心性的值,我們想要得到的是中介度中心性的排名,因此,我們設計一個有效率的方法去合併點來得到一個比較少點和邊的網路,然後就去估計每個點的中介度中心性,便可取得中介度中心性的排名。
Centralities are crucial in quantifying the roles and the position of vertices in social networks. The betweenness centrality of a vertex is based on the number of shortest paths passing through it. However, the computation of betweenness centrality is expensive. In many practical applications, the ranking of betweenness centralities is more importance than the exact values, so we developed a novel algorithm that efficiently combines vertices to reduce the size of the network. Then, we compute vertices of high betweenness centralities quickly in the modified network to get the top-k vertices.
1 Introduction
2 Related works
2.1 Brandes algorithm
2.2 Pivot method
2.3 The method of high degree
2.4 The method of utilizing the novel properties of biconnected components
2.5 Group testing in identifying high betweenness centrality vertices 9
3 Methods
4 Experiments
4.1 Evaluating the results
4.2 Test data
4.3 Results
5 Conclusions

[1] Béla Bollobás. Modern graph theory. Springer, 1998.
[2] Ulrik Brandes. A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology, 25(2):163–177, 2001.
[3] Ulrik Brandes and Christian Pich. Centrality estimation in large networks. International Journal of Bifurcation and Chaos,17(07):2303–2318, 2007.
[4] W.H.Chong, W.S.B.Toh, and L.N.Teow. Efficient extraction of high betweenness vertices. In 2010 International Conference on Advances in Social Networks Analysis and Mining, pages 286–290, Aug 2010.
[5] Reinhard Diestel. Graph Theory. Springer, 2005.
[6] Jean-Christophe Filliâtre and Claude Marché. KONECT Datasets: the Koblenz Network Collection. http://konect.uni-koblenz.de/ networks/.
[7] Min-Joong Lee and Chin-Wan Chung. Finding k-highest betweenness centrality vertices in graphs. In Proceedings of the 23rd International Conference on World Wide Web, WWW ’14 Companion, pages 339–340, New York, NY, USA, 2014. ACM.
[8] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection.
[9] Vladimir Ufimtsev and Sanjukta Bhowmick. Application of group testing in identifying high betweenness centrality vertices in complex networks. In Eleventh Workshop on Mining and Learning with Graphs, pages 1–8, 2013
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文