# 臺灣博碩士論文加值系統

(3.236.50.201) 您好！臺灣時間：2021/08/06 09:29

:::

### 詳目顯示

:
 Twitter

• 被引用: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 Introduction2 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 93 Methods4 Experiments 4.1 Evaluating the results 4.2 Test data 4.3 Results5 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. Eﬃcient 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 Uﬁmtsev 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
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 無相關點閱論文

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室