㈠ 用什麼程序實現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用來衡量一個網