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

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

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