㈠ 用什么程序实现pagerank算法
you can get it in GitHub,a website.
/**
* @file
* @author Aapo Kyrola <[email protected]>
* @version 1.0
*
* @section LICENSE
*
* Copyright [2012] [Aapo Kyrola, Guy Blelloch, Carlos Guestrin / Carnegie Mellon University]
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
* @section DESCRIPTION
*
* Simple pagerank implementation. Uses the basic vertex-based API for
* demonstration purposes. A faster implementation uses the functional API,
* "pagerank_functional".
*/
#include <string>
#include <fstream>
#include <cmath>
#define GRAPHCHI_DISABLE_COMPRESSION
#include "graphchi_basic_includes.hpp"
#include "util/toplist.hpp"
using namespace graphchi;
#define THRESHOLD 1e-1
#define RANDOMRESETPROB 0.15
typedef float VertexDataType;
typedef float EdgeDataType;
struct PagerankProgram : public GraphChiProgram<VertexDataType, EdgeDataType> {
/**
* Called before an iteration starts. Not implemented.
*/
void before_iteration(int iteration, graphchi_context &info) {
}
/**
* Called after an iteration has finished. Not implemented.
*/
void after_iteration(int iteration, graphchi_context &ginfo) {
}
/**
* Called before an execution interval is started. Not implemented.
*/
void before_exec_interval(vid_t window_st, vid_t window_en, graphchi_context &ginfo) {
}
/**
* Pagerank update function.
*/
void update(graphchi_vertex<VertexDataType, EdgeDataType> &v, graphchi_context &ginfo) {
float sum=0;
if (ginfo.iteration == 0) {
/* On first iteration, initialize vertex and out-edges.
The initialization is important,
because on every run, GraphChi will modify the data in the edges on disk.
*/
for(int i=0; i < v.num_outedges(); i++) {
graphchi_edge<float> * edge = v.outedge(i);
edge->set_data(1.0 / v.num_outedges());
}
v.set_data(RANDOMRESETPROB);
} else {
/* Compute the sum of neighbors' weighted pageranks by
reading from the in-edges. */
for(int i=0; i < v.num_inedges(); i++) {
float val = v.inedge(i)->get_data();
sum += val;
}
/* Compute my pagerank */
float pagerank = RANDOMRESETPROB + (1 - RANDOMRESETPROB) * sum;
/* Write my pagerank divided by the number of out-edges to
each of my out-edges. */
if (v.num_outedges() > 0) {
float pagerankcont = pagerank / v.num_outedges();
for(int i=0; i < v.num_outedges(); i++) {
graphchi_edge<float> * edge = v.outedge(i);
edge->set_data(pagerankcont);
}
}
/* Keep track of the progression of the computation.
GraphChi engine writes a file filename.deltalog. */
ginfo.log_change(std::abs(pagerank - v.get_data()));
/* Set my new pagerank as the vertex value */
v.set_data(pagerank);
}
}
};
/**
* Faster version of pagerank which holds vertices in memory. Used only if the number
* of vertices is small enough.
*/
struct PagerankProgramInmem : public GraphChiProgram<VertexDataType, EdgeDataType> {
std::vector<EdgeDataType> pr;
PagerankProgramInmem(int nvertices) : pr(nvertices, RANDOMRESETPROB) {}
void update(graphchi_vertex<VertexDataType, EdgeDataType> &v, graphchi_context &ginfo) {
if (ginfo.iteration > 0) {
float sum=0;
for(int i=0; i < v.num_inedges(); i++) {
sum += pr[v.inedge(i)->vertexid];
}
if (v.outc > 0) {
pr[v.id()] = (RANDOMRESETPROB + (1 - RANDOMRESETPROB) * sum) / v.outc;
} else {
pr[v.id()] = (RANDOMRESETPROB + (1 - RANDOMRESETPROB) * sum);
}
} else if (ginfo.iteration == 0) {
if (v.outc > 0) pr[v.id()] = 1.0f / v.outc;
}
if (ginfo.iteration == ginfo.num_iterations - 1) {
/* On last iteration, multiply pr by degree and store the result */
v.set_data(v.outc > 0 ? pr[v.id()] * v.outc : pr[v.id()]);
}
}
};
int main(int argc, const char ** argv) {
graphchi_init(argc, argv);
metrics m("pagerank");
global_logger().set_log_level(LOG_DEBUG);
/* Parameters */
std::string filename = get_option_string("file"); // Base filename
int niters = get_option_int("niters", 4);
bool scheler = false; // Non-dynamic version of pagerank.
int ntop = get_option_int("top", 20);
/* Process input file - if not already preprocessed */
int nshards = convert_if_notexists<EdgeDataType>(filename, get_option_string("nshards", "auto"));
/* Run */
graphchi_engine<float, float> engine(filename, nshards, scheler, m);
engine.set_modifies_inedges(false); // Improves I/O performance.
bool inmemmode = engine.num_vertices() * sizeof(EdgeDataType) < (size_t)engine.get_membudget_mb() * 1024L * 1024L;
if (inmemmode) {
logstream(LOG_INFO) << "Running Pagerank by holding vertices in-memory mode!" << std::endl;
engine.set_modifies_outedges(false);
engine.set_disable_outedges(true);
engine.set_only_adjacency(true);
PagerankProgramInmem program(engine.num_vertices());
engine.run(program, niters);
} else {
PagerankProgram program;
engine.run(program, niters);
}
/* Output top ranked vertices */
std::vector< vertex_value<float> > top = get_top_vertices<float>(filename, ntop);
std::cout << "Print top " << ntop << " vertices:" << std::endl;
for(int i=0; i < (int)top.size(); i++) {
std::cout << (i+1) << ". " << top[i].vertex << "\t" << top[i].value << std::endl;
}
metrics_report(m);
return 0;
}试试吧！
㈡ maprece 和 spark 的pagerank算法一样吗
，之所以加了0.25是因为初始的概率为1/n，而n为网站数，这里统计网站数又得需要一个MapRece来实现，所以作罢，权当n是手工输入的。
由于每次迭代后的结果只能放在文件中，所以这里花了很多时间在规范如何输出，以及map和rece之间如何传值的问题。
在map中，我们要做的是从输入文件中获取alaph和每个网站的转移概率。例如
A 0.25:B,C,D
B的转移概率为1/3而且是从A转向B的
㈢ PageRank 算法的复杂程度怎么样
PageRank在算法和数学上并不复杂，具体描述可见http://en.wikipedia.org/wiki/PageRank 。在做web级别的计算时，主要的挑战来自海量的数据，需要有大规模并行计算技术的支持。因为PageRank存在的缺陷，现已为更高级的模型（可参见HITS和TrustRank）取代。
㈣ 求百度的超链分析和Google的pagerank技术的区别，要权威的
== 这是 中国WEB信息博物馆 （Web InfoMall） 2003年10月09日 存储的网页 == 点击这里查看本网页的其他版本 请选择: 2003年10月09日 2004年05月04日 当前最新网页 隐藏InfoMall信息 -------------------------------------------------------------------------------- 转到主要内容 竹笋炒肉 东坡有诗“无竹则俗，无肉则廋；不俗不廋，竹笋炒肉”。：） 欢迎光临的每一位朋友。这是我的第一个BLOG，用来记录我的所学、所做、所思、所想、所经历、所感受。 « Log4J学习笔记（3） | Main | Google的PageRank算法学习(2) » August 28, 2003 Google的PageRank算法学习 据车东在CNBLOG推荐文章，作的学习笔记。 1、PageRank(网页级别)的概念 互联网发展早期的搜索引擎，对web页面的排序，是根据搜索的词组（短语）在页面中的出现次数（occurence ），并用页面长度和html标签的重要性提示等进行权重修订。链接名气(link popularity)技术通过其它文档链接到当前页面（inbound links）的链接数量来决定当前页的重要性，这样可以有效地抵制被人为加工的页面欺骗搜索引擎的手法。 PageRank计算页面的重要性，对每个链入(inbound)赋以不同的权值，链接提供页面的越重要则此链接入越高。当前页的重要性，是由其它页面的重要性决定的。 2、PageRank算法1 PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) 其中：PR(A):页面A的网页级别, PR(Ti)：页面Ti的网页级别，页面Ti链向页面A， C(Ti)：页面Ti链出的链接数量， d：阻尼系数，取值在0－1之间. 由此可见，1）这个算法不以站点排序，页面网页级别由一个个独立的页面决定；2）页面的网页级别由链向它的页面的网页级别决定，但每个链入页面的贡献的值是不同的。如果Ti页面中链出越多，它对当前页面A的贡献就越小。A的链入页面越多，其网页级别也越高；3）阻尼系数的使用，减少了其它页面对当前页面A的排序贡献。 3、随机冲浪模型 Lawrence Page 和 Sergey Brin 提出了用户行为的随机冲浪模型，来解释上述算法。他们把用户点击链接的行为，视为一种不关心内容的随机行为。而用户点击页面内的链接的概率，完全由页面上链接数量的多少决定的，这也是上面PR(Ti)/C(Ti)的原因。一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。阻尼系数d的引入，是因为用户不可能无限的点击链接，常常因劳累而随机跳入另一个页面。d可以视为用户无限点击下去的概率，（1－d）则就是页面本身所具有的网页级别。 4、PageRank算法2（对算法1的修订） PR(A) = (1-d) / N + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) 其中N是互联网上所有网页的数量 由此，所有页面的网页级别形成的一个概率分布，所有页面的网页级别之和是1。在算法1中，随机冲浪访问某个页面的概率由互联网的总页数决定，在算法2中，网页级别是一个页面被随机访问的期望值。 以下讲解，皆基于算法1，主要是计算简单，因为不用考虑N的值。 5、PageRank的特性 所有页面的网页级别之和等于互联网的总页数。在网页数比较少的情况下，网页级别方程可以解出，而面对互联网上成亿的网页，再解方程是不可能的。 此处设阻尼系数为0.5，虽然Lawrence Page 和 Sergey Brin在实际将其设为0.85. PR(A) = 0.5 + 0.5 PR(C) PR(B) = 0.5 + 0.5 (PR(A) / 2) PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B)) 解得： PR(A) = 14/13 = 1.07692308 PR(B) = 10/13 = 0.7692307
㈤ pagerrank算法有何应用
．017 基于中心性和PageRank的网页综合评分方法 （1．西南交通大学信息科学与技术学院，四川成都610031；2．成都市公安局科技处，四川成都610017；3．西南财经大学经济信息工程学院，四川成都610074） 摘要：为准确、高效地对网页进行评分，提出了一种基于中心性（结点度、居间度和紧密度）和PageRank算法 的网页评分方法CentralRank．它采用PageRank算法计算网页分数，借助中心性度量的方法计算页面在Web社会 网络中的重要性．为了验证CentralRank的性能优势，设计了一个网页抓取器，可利用该抓取器自动、准确地下载 网页信息．该网页抓取器集成了网络信息采集、页面内容分析和页面消重3项技术．基于大量真实数据的实验结 果表明：CentralRank在保证网页评分时间性能的前提下，比单纯基于中心性的网页评分算法和PageRank算法更 准确、有效，预测准确性分别提高约14．2％和7．5％． 关键词：社会网络分析；Web社会网络；中心性；PageRank算法；网页评分 中图分类号：TP311．13 文献标志码：A Hybrid Page Scoring Algorithm Based PageRankqtAO Shaojiel，PENG Jin92，H Tianruil，LI Iton91，12 Taiyon93，WANG Cha01 （1．School InformationScience Technology，SouthwestJiaotong University，Cheng 610031，China； 2．Department Technology，ChengMunicipal Public Security Bureau，Cheng 610017，China； 3．School EconomicInformation Engineering，soutllwtem University Economics，Cheng610074， China） Abst豫ct：In order scor
㈥ pagerank算法主要基于什么对结果进行排序
它是Google排名运算法则（排名公式）的一部分，是Google用于用来标识网页的等级/重要性的一种方法，是Google用来衡量一个网站的好坏的唯一标准。在揉合了诸如Title标识和Keywords标识等所有其它因素之后，Google通过PageRank来调整结果，使那些更具“等级/重要性”的网页在搜索结果中另网站排名获得提升，从而提高搜索结果的相关性和质量。 PageRank(网页级别)，2001年9月被授予美国专利，专利人是Google创始人之一拉里·佩奇 PageRank专利人——拉里·佩奇 （Larry Page）。因此，PageRank里的page不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。它是Google排名运算法则（排名公式）的一部分，是Google用于用来标识网页的等级/重要性的一种方法，是Google用来衡量一个网站的好坏的唯一标准
㈦ google用自己的pagerank算法，百度用的什么算法呢
网络最新系统是凤巢。具体算法不会披露的。
㈧ 我们老师要求我们用C语言模拟pagerank算法，因为要连续读入我想做一下文件读入的优化，请问有什么方法谢
一次读入8k字节，放到缓冲区，可大大加快读取速度
例如要读入10字节，则程序先读8k到内存中，返回10字节，下次调用读取时，直接从内存中返回，这样就快多了
㈨ pagerank算法总是会收敛么
这pagerank算法是个很复杂的算法
㈩ pagerank算法可以用来干什么
目前很多重要的链接分析算法都是在PageRank算法基础上衍生出来的。PageRank是Google用于用来标识网页的等级/重要性的一种方法,是Google用来衡量一个网