軟件設(shè)計(jì)與實(shí)踐實(shí)驗(yàn)報(bào)告

1、軟件設(shè)計(jì)與實(shí)踐實(shí)驗(yàn)報(bào)告1、 論文題目： Toward Efficient Simrank Computation on Large Network2、論文概要：simrank 是一種通過評(píng)估圖中點(diǎn)的相似性來拓普性地簡(jiǎn)化圖的模型。SimRank 模型定義兩個(gè)頁(yè)面的相似度是基于下面的遞歸思想：如果指向結(jié)點(diǎn)和指向結(jié)點(diǎn)的結(jié)點(diǎn)相似，那么和也認(rèn)為是相似的。這個(gè)遞歸定義的初始條件是：每個(gè)結(jié)點(diǎn)與它自身最相似。例子如下：啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊頂頂頂頂頂

2、頂頂頂頂頂頂頂頂頂頂發(fā)嘎嘎嘎嘎嘎嘎嘎嘎灌灌灌灌灌灌灌灌灌灌灌灌灌灌灌反反復(fù)復(fù)反反復(fù)復(fù)反反復(fù)復(fù)反反復(fù)復(fù)反反復(fù)復(fù)反反復(fù)復(fù)反反復(fù)復(fù)發(fā)多少頂頂頂頂頂頂頂頂頂頂頂頂頂頂頂頂頂頂水水水水水水水水水水水水水水水水水水水水是雙方都阿頂頂頂頂頂頂頂頂頂頂頂頂頂頂頂頂頂頂頂頂頂頂?shù)鄬?duì)于A和B，面粉和糖的鏈接就沒有那么緊密，所以這里引入相似度（0.0-1.0）的概念來評(píng)估這種情況。算法的時(shí)間復(fù)雜度為kmn（最好）到kn3（最差）。算法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：SimRank算法僅利用的網(wǎng)絡(luò)的結(jié)構(gòu)信息來計(jì)算任意兩點(diǎn)間的相似度，而不必考慮節(jié)點(diǎn)所包含的內(nèi)容。即拓?fù)湫裕恍枰紤]過多的冗余信息。缺點(diǎn)： 1）SimRank僅關(guān)注的是

3、具有對(duì)稱路徑的兩點(diǎn)間的相似度。 2）SimRank的計(jì)算復(fù)雜度較高由于其自指性，面對(duì)大數(shù)據(jù)就會(huì)遇到挑戰(zhàn)。先進(jìn)的想法認(rèn)為，算法的時(shí)間復(fù)雜度為Kmn，其中，k是迭代次數(shù)，n個(gè)頂點(diǎn)m條邊。而所謂部分記憶可以減少重復(fù)計(jì)算，即緩存其中一部分相似以重用。此外在準(zhǔn)確性方面，現(xiàn)有的simrank需要logC次迭代，c為阻尼系數(shù)。盡管如此，這樣的幾何收斂的精度是可取的。在本文中,我們解決這些差異。(1)我們提出一個(gè)自適應(yīng)聚類策略來消除冗余部分（部分求和中的重復(fù)）設(shè)計(jì)一個(gè)高效的算法使Simrank復(fù)雜度減少至K（dn2），d是遠(yuǎn)遠(yuǎn)小于的圖的平均入度(2)我們也設(shè)計(jì)了一個(gè)新的SimRank,基于微分方程的概念,可以

4、表示為一個(gè)指數(shù)的總和轉(zhuǎn)換矩陣,而不是幾何之和傳統(tǒng)的同行。這就導(dǎo)致進(jìn)一步加速SimRank迭代的收斂速度。(3)使用真實(shí)的和合成數(shù)據(jù),我們部分的實(shí)證驗(yàn)證我們的方法總體上優(yōu)于最普遍的算法了一個(gè)數(shù)量級(jí),那我們修訂SimRank的概念進(jìn)一步達(dá)到5倍加速圖,同時(shí)也相當(dāng)大保留原始SimRank的相對(duì)順序。介紹：基于超鏈接結(jié)構(gòu)的識(shí)別相似對(duì)象是許多網(wǎng)絡(luò)數(shù)據(jù)挖掘的基本手法。例子包括網(wǎng)頁(yè)排名超聚類協(xié)同過濾超文本分類。在過去十年里，有一個(gè)日益增長(zhǎng)的需求要求在大圖里自動(dòng)的高效地評(píng)估對(duì)象相似性。事實(shí)上，網(wǎng)絡(luò)有很大的維度，并且更新的很快，所以需要更快的評(píng)估速度。simrank是現(xiàn)有的極為強(qiáng)大的評(píng)估對(duì)象相似性的工具。類似于

5、眾所周知的pagerank，simrank僅依賴于網(wǎng)絡(luò)中的鏈接關(guān)系，而非對(duì)象文本等內(nèi)容。而兩者的區(qū)別在于，p為對(duì)象分配權(quán)重，s則是根據(jù)相似度給出評(píng)分。simrank 被Jeh和Widom首次提出，并享有極高的人氣。在很多領(lǐng)域都有他的身影，如推薦系統(tǒng)，topk搜索。SimRank 模型定義兩個(gè)頁(yè)面的相似度是基于下面的遞歸思想：如果指向結(jié)點(diǎn)和指向結(jié)點(diǎn)的結(jié)點(diǎn)相似，那么和也認(rèn)為是相似的。這個(gè)遞歸定義的初始條件是：每個(gè)結(jié)點(diǎn)與它自身最相似。算法的時(shí)間復(fù)雜度為kmn（最好）到kn3（最差）。而所謂的部分歸納記憶，是一種類似緩存的方法，她可以減少重復(fù)計(jì)算。 此外，論文還就時(shí)間和空間討論了幾種simrank的優(yōu)

6、劣3、 算法實(shí)現(xiàn)算法實(shí)現(xiàn)分為如下幾步A、 簡(jiǎn)化論文中網(wǎng)頁(yè)模型關(guān)系為圖中結(jié)點(diǎn)間的有向鏈接關(guān)系；B、 圖的輸入：從文件中讀入圖，以鄰接矩陣形式存儲(chǔ)，同時(shí)建立n*n矩陣，以存儲(chǔ)兩點(diǎn)間相似度評(píng)分C、 SIMRANK評(píng)分的生成;通過公式生成圖中各點(diǎn)間相似度評(píng)分，并記錄在矩陣中；D、 輸出：結(jié)果的輸出：4、 心得體會(huì)通過這次特別的學(xué)習(xí)過程，我掌握了閱讀論文的基本常識(shí)，熟練了各種數(shù)據(jù)結(jié)構(gòu)的使用以及算法設(shè)計(jì)的流程，也同時(shí)學(xué)習(xí)了JAVA語言的使用。在學(xué)習(xí)中我也遇到了很多不大不小的困難需要一步步去解決，比如數(shù)據(jù)流的傳遞，函數(shù)包的使用等。雖然有些問題仍然不能實(shí)現(xiàn)，做出了妥協(xié)，但事實(shí)上，尋求問題的解答這個(gè)過程本身就是

7、一種學(xué)習(xí)、成長(zhǎng)。5、 代碼package hty.simrank;import java.io.BufferedReader;import java.io.File;import java.io.FileNotFoundException;import java.io.FileReader;import java.io.IOException;import java.text.DecimalFormat;import java.util.HashMap;public class MySimRank public HashMap queriesIdMap = new HashMap();publ

8、ic Integer queryIdGen = 1;public HashMap adsIdMap = new HashMap();public Integer adIdGen = 1;/ public HashMapInteger,ArrayList linksMap = new/ HashMapInteger,ArrayList();/ public HashMapInteger,ArrayList queryScore = new/ HashMapInteger,ArrayList();/ public HashMapInteger,ArrayList adScore = new/ Ha

9、shMapInteger,ArrayList();public Double queryScoreK = new Double100100;public Double queryScore = new Double100100;public Double adScore = new Double100100;public Integer linksAry = new Integer100100;public void loadGraphFromFile(File file) throws IOException BufferedReader reader = new BufferedReade

10、r(new FileReader(file);String line;while (line = reader.readLine() != null) int index1 = line.indexOf(-);if (index1 = -1) continue;String links = line.split(-);String query = links0;String adsStr = links1;String ads = adsStr.split(;);for (int i = 0; i ads.length; i+) if (adsIdMap.get(adsi) != null)

11、linksAryqueryIdGenadsIdMap.get(adsi) = 1; else adsIdMap.put(adsi, adIdGen);linksAryqueryIdGenadIdGen = 1;adIdGen+;if (linksAry0adsIdMap.get(adsi) = null) linksAry0adsIdMap.get(adsi) = 0;linksAry0adsIdMap.get(adsi) += 1;if (linksAryqueryIdGen0 = null) linksAryqueryIdGen0 = 0;linksAryqueryIdGen0 += 1;

12、queriesIdMap.put(queryIdGen, query);queryIdGen+;reader.close();public void initScore() / queryScorefor (int i = 0; i queryIdGen; i+) for (int j = 0; j queryIdGen; j+) if (i = j)queryScoreij = 1.0;queryScoreKij = 1.0;elsequeryScoreij = 0.0;queryScoreKij = 0.0;/ adScorefor (int i = 0; i adIdGen; i+) f

13、or (int j = 0; j adIdGen; j+) if (i = j)adScoreij = 1.0;elseadScoreij = 0.0;public void getSimRankScore(double c) / 計(jì)算query scorefor (int i = 1; i queryIdGen; i+) int numOfQuery1 = linksAryi0;for (int j = i + 1; j queryIdGen; j+) int numOfQuery2 = linksAryj0;double scoreTemp = c / (numOfQuery1 * num

14、OfQuery2);scoreTemp *= getAdsSimilar(i, j);queryScoreji = scoreTemp;queryScoreij = scoreTemp;/計(jì)算ad score,用queryScoreK計(jì)算for (int i = 1; i adIdGen; i+) int numOfAd1 = linksAry0i;for (int j = i + 1; j adIdGen; j+) int numOfAd2 = linksAry0j;System.out.println(= + numOfAd1 + | +numOfAd2);double scoreTemp

15、 = c / (numOfAd1 * numOfAd2);scoreTemp *= getQuerySimilar(i, j);adScoreji = scoreTemp;adScoreij = scoreTemp;/將queryScore復(fù)制到queryScoreK中copyQueryScore();public void copyQueryScore()for(int i=0;iqueryIdGen;i+)queryScoreKi = queryScorei.clone();public double getQuerySimilar(int ad1, int ad2)double resu

16、lt = 0;int numOfAd1 = linksAry0ad1;int numOfAd2 = linksAry0ad2;int count1 = 0;int count2 = 0;for (int i = 1; i adIdGen; i+) if (linksAryiad1 != null) count1+;count2 = 0;for (int j = 1; j numOfAd2) break;if (count1 numOfAd1) break;return result;public double getAdsSimilar(int query1, int query2) doub

17、le result = 0;int numOfQuery1 = linksAryquery10;int numOfQuery2 = linksAryquery20;int count1 = 0;int count2 = 0;for (int i = 1; i adIdGen; i+) if (linksAryquery1i != null) count1+;count2 = 0;for (int j = 1; j numOfQuery2) break;if (count1 numOfQuery1) break;return result;public void outputScore(Deci

18、malFormat df) / 輸出結(jié)果System.out.println(查詢間的相似度:);for (int i = 1; i queryIdGen; i+) for (int j = 1; j queryIdGen; j+) System.out.print(df.format(queryScoreij) + t);System.out.print(n);System.out.print(n);System.out.println(廣告間的相似度:);for (int i = 1; i adIdGen; i+) for (int j = 1; j adIdGen; j+) System.out.print(df.format(adScoreij) + t);System.out.print(n);System.out.print(nn);public static void main(String args) throws FileNotFoundException,IOException MySimRank mySimRank = new MySimRank();mySimRank.loadGraphFromFile