軟件設計與實踐實驗報告

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

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

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

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

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

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

7、一種學習、成長。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) / 計算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;/計算ad score,用queryScoreK計算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復制到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