软件设计与实践实验报告

1、软件设计与实践实验报告1、 论文题目： Toward Efficient Simrank Computation on Large Network2、论文概要：simrank 是一种通过评估图中点的相似性来拓普性地简化图的模型。SimRank 模型定义两个页面的相似度是基于下面的递归思想：如果指向结点和指向结点的结点相似，那么和也认为是相似的。这个递归定义的初始条件是：每个结点与它自身最相似。例子如下：啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊顶顶顶顶顶

2、顶顶顶顶顶顶顶顶顶顶发嘎嘎嘎嘎嘎嘎嘎嘎灌灌灌灌灌灌灌灌灌灌灌灌灌灌灌反反复复反反复复反反复复反反复复反反复复反反复复反反复复发多少顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶水水水水水水水水水水水水水水水水水水水水是双方都阿顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶但相对于A和B，面粉和糖的链接就没有那么紧密，所以这里引入相似度（0.0-1.0）的概念来评估这种情况。算法的时间复杂度为kmn（最好）到kn3（最差）。算法的优缺点：优点：SimRank算法仅利用的网络的结构信息来计算任意两点间的相似度，而不必考虑节点所包含的内容。即拓扑性，不需要考虑过多的冗余信息。缺点： 1）SimRank仅关注的是

3、具有对称路径的两点间的相似度。 2）SimRank的计算复杂度较高由于其自指性，面对大数据就会遇到挑战。先进的想法认为，算法的时间复杂度为Kmn，其中，k是迭代次数，n个顶点m条边。而所谓部分记忆可以减少重复计算，即缓存其中一部分相似以重用。此外在准确性方面，现有的simrank需要logC次迭代，c为阻尼系数。尽管如此，这样的几何收敛的精度是可取的。在本文中,我们解决这些差异。(1)我们提出一个自适应聚类策略来消除冗余部分（部分求和中的重复）设计一个高效的算法使Simrank复杂度减少至K（dn2），d是远远小于的图的平均入度(2)我们也设计了一个新的SimRank,基于微分方程的概念,可以

4、表示为一个指数的总和转换矩阵,而不是几何之和传统的同行。这就导致进一步加速SimRank迭代的收敛速度。(3)使用真实的和合成数据,我们部分的实证验证我们的方法总体上优于最普遍的算法了一个数量级,那我们修订SimRank的概念进一步达到5倍加速图,同时也相当大保留原始SimRank的相对顺序。介绍：基于超链接结构的识别相似对象是许多网络数据挖掘的基本手法。例子包括网页排名超聚类协同过滤超文本分类。在过去十年里，有一个日益增长的需求要求在大图里自动的高效地评估对象相似性。事实上，网络有很大的维度，并且更新的很快，所以需要更快的评估速度。simrank是现有的极为强大的评估对象相似性的工具。类似于

5、众所周知的pagerank，simrank仅依赖于网络中的链接关系，而非对象文本等内容。而两者的区别在于，p为对象分配权重，s则是根据相似度给出评分。simrank 被Jeh和Widom首次提出，并享有极高的人气。在很多领域都有他的身影，如推荐系统，topk搜索。SimRank 模型定义两个页面的相似度是基于下面的递归思想：如果指向结点和指向结点的结点相似，那么和也认为是相似的。这个递归定义的初始条件是：每个结点与它自身最相似。算法的时间复杂度为kmn（最好）到kn3（最差）。而所谓的部分归纳记忆，是一种类似缓存的方法，她可以减少重复计算。 此外，论文还就时间和空间讨论了几种simrank的优

6、劣3、 算法实现算法实现分为如下几步A、 简化论文中网页模型关系为图中结点间的有向链接关系；B、 图的输入：从文件中读入图，以邻接矩阵形式存储，同时建立n*n矩阵，以存储两点间相似度评分C、 SIMRANK评分的生成;通过公式生成图中各点间相似度评分，并记录在矩阵中；D、 输出：结果的输出：4、 心得体会通过这次特别的学习过程，我掌握了阅读论文的基本常识，熟练了各种数据结构的使用以及算法设计的流程，也同时学习了JAVA语言的使用。在学习中我也遇到了很多不大不小的困难需要一步步去解决，比如数据流的传递，函数包的使用等。虽然有些问题仍然不能实现，做出了妥协，但事实上，寻求问题的解答这个过程本身就是

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) / 输出结果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