Top-k中心度查詢算法研究.pdf

1、如何快速地找出中心度最高的k個點是有關(guān)圖模型研究的熱點問題之一，在現(xiàn)實生活中有著廣泛的應(yīng)用，比如超市選址、城市規(guī)劃、熱點新聞報道、數(shù)據(jù)挖掘以及病毒營銷策略等。通過對現(xiàn)有方法進(jìn)行分析，發(fā)現(xiàn)現(xiàn)有方法的低效性主要是由于頂點處理順序的代價過高和處理頂點數(shù)量過多造成的。本文針對現(xiàn)有中心度計算方法效率低的問題展開研究，具體內(nèi)容如下。
　　首先，針對頂點處理順序的代價過高提出一種基于拓?fù)渑判虻膖op-k中心度查詢算法。該算法采用拓?fù)漤樞蛱娲延?/p>

2、方法的頂點處理順序，減少已有方法求解頂點處理順序所帶來的昂貴的時間代價。其優(yōu)點是簡單、高效，但是應(yīng)用具有一定的局限性，對于結(jié)構(gòu)比較復(fù)雜的圖計算代價會很高。
　　其次，針對處理頂點數(shù)量過多的問題，提出基于估算篩選的中心度查詢算法。該算法通過一次廣度優(yōu)先遍歷估算出每個點中心度的上界值，通過上界值的大小確定頂點的處理順序。在計算過程中，通過維護(hù)top-k中心度的真實值，可以有效地過濾掉無需計算中心度真實值的點，使候選集需要計算真實中心度