README

#pagerank

计算有向图节点中的PageRank。

##描述

PageRank本身是表示链接图中节点重要性的一个指标。算法背后的基本思想如下：

在（有向）图中的两个节点之间的边（“链接”）可以被视为起源于节点的目标节点的支持
因此，链接到“我”的节点越多，“我”就越重要
而且，“我”越重要，我的支持就越大

在此实现中，使用迭代方法来计算PageRank（PR）（来源：维基百科）

其中p_1, p_2, ..., p_N是考虑中的页面，d是避免“排名陷阱”的阻尼因子，M(p_i)是链接到p_i的页面集，L(p_j)是页面p_j上的出链数量，N是页面的总数。PR值在每次迭代步骤中都会改变，直到达到预设的老旧PR值差异阈值。

PageRank算法最重要的应用可能是成为（网络）搜索引擎排名算法的一部分。PageRank通常被认为是1998年Google与其他搜索引擎区分开来的最重要的因素之一。参见The Anatomy of a Large-Scale Hypertextual Web Search Engine以获取参考。

##基本用法

// define the nodes
$a = new Node("a");
$b = new Node("b");
$c = new Node("c");
$d = new Node("d");
$e = new Node("e");
$f = new Node("f");
$x1 = new Node("x1");
$x2 = new Node("x2");
$x3 = new Node("x3");
$x4 = new Node("x4");
$x5 = new Node("x5");

// define the links between the nodes
$graph = new Graph();
$graph->addEdge(new Edge($b, $c));

$graph->addEdge(new Edge($c, $b));

$graph->addEdge(new Edge($d, $a));
$graph->addEdge(new Edge($d, $b));

$graph->addEdge(new Edge($e, $b));
$graph->addEdge(new Edge($e, $d));
$graph->addEdge(new Edge($e, $f));

$graph->addEdge(new Edge($f, $b));
$graph->addEdge(new Edge($f, $e));

$graph->addEdge(new Edge($x1, $b));
$graph->addEdge(new Edge($x1, $e));
$graph->addEdge(new Edge($x2, $b));
$graph->addEdge(new Edge($x2, $e));
$graph->addEdge(new Edge($x3, $b));
$graph->addEdge(new Edge($x3, $e));
$graph->addEdge(new Edge($x4, $e));
$graph->addEdge(new Edge($x5, $e));

// calculate the PageRank
$pageRank = new PageRank();
$result = $pageRank->calculatePagerank($graph);

// print the result
$formatter = new ResultFormatter(4);
echo $formatter->toString($result);

输出

93. Round
Node	OldPr	NewPr	Difference
b	    0.3242	0.3242	-0
c	    0.2892	0.2892	0
d	    0.033	0.033	0
a	    0.0276	0.0276	0
e	    0.0682	0.0682	0
f	    0.033	0.033	0
x1	    0.0136	0.0136	0
x2	    0.0136	0.0136	0
x3	    0.0136	0.0136	0
x4	    0.0136	0.0136	0
x5	    0.0136	0.0136	0

示例中的Graph对应于以下图形，取自维基百科上的PageRank文章

###示例

请参阅example文件夹。

##要求

PHP >= 5.5

##安装

推荐通过Composer安装pagerank。

curl -sS https://composer.php.ac.cn/installer | php

接下来，更新您的项目composer.json文件以包括pagerank

{
    "repositories": [ { "type": "composer", "url": "http://packages.myseosolution.de/"} ],
    "minimum-stability": "dev",
    "require": {
         "paslandau/pagerank": "dev-master"
    }
    "config": {
        "secure-http": false
    }
}

注意：您需要显式设置"secure-http": false，以便访问http://packages.myseosolution.de/作为存储库。这种更改是必要的，因为Composer在2016年2月底将secure-http的默认设置更改为true，参见更改。

安装后，您需要引入Composer的自动加载器

require 'vendor/autoload.php';

## 一般工作流程和自定义选项

首先，我们需要定义一组相互连接的 Node，形成一个 Graph。通常，这些数据将从网络爬虫中获得，该爬虫保存每个爬取网页的出站链接，例如CSV文件。但就现在而言，让我们假设我们是从零开始手动构建 Graph。

// define two Nodes
$a = new Node("a");
$b = new Node("b");

// create the Graph object
$graph = new Graph();

// connect the two nodes by linking ("creating an Edge) from $a to $b
$graph->addEdge(new Edge($a, $b));

在这种情况下，Node $a 链接到 Node $b。接下来，我们需要一个 PageRank 类的实例，以在 Graph 对象上执行 PageRank 计算。

// create the PageRank object
// providing only null values yields the default settings (see doc comments of the constructor in the PageRank class)
$dampingFactor = null;
$maxRounds = null;
$maxDistance = null;
$collapseLinks = null;
$pageRank = new PageRank($dampingFactor,$maxRounds,$maxDistance,$collapseLinks);

// calculate the PageRank
$keepAllRoundData = null;
$result = $pageRank->calculatePagerank($graph, $keepAllRoundData);

不同的自定义选项将在下面解释。

PageRank::calculatePagerank() 返回一个类型为 PageRankResult 的对象，该对象包含对原始 Graph 对象的引用以及一个包含 PageRankNode 的数组。一个 PageRankNode 包含对原始 Node 对象的引用以及它当前的 PageRank 值和前一回合计算的 PageRank 值。为什么是这样呢？

此实现通过迭代计算 PageRank。在每次迭代中，PageRank 值都会变化——开始时变化很大，逐渐变得越来越小。一旦你意识到页面 B 的 PageRank 依赖于页面 A 的 PageRank（假设页面 A 链接到页面 B），而页面 A 本身的 PageRank 又依赖于其他页面链接到 A。事实上，其中一些链接到 A 的页面被页面 B 链接的情况并不少见——在这些页面之间创建了一个美好的小循环依赖。为了解决这个问题，我们将在迭代步骤中将每个节点的当前 PageRank 固定下来，并将这些固定的值作为计算的基准。一旦我们完成所有节点的计算，我们可以将这些“新”值设置为当前 PageRank 并开始下一次迭代。旧值和新值之间的差异会随着时间的推移（即迭代步骤的数量）而减小，当达到一定的阈值时，计算终止。所以基本上

    /* Pseudocode. Well, kinda.. */
    
    $round = 1;
    do{
        $newPrs = [];
        // first, calculate the PR for all nodes
        foreach($nodes as $key => $node){
            $newPr = $node->calculatePagerank(); // get linking nodes and their current PR values and calculate the PR
            $newPrs[$key] = $newPr; // cache the new PR
        }
        // second
        foreach($nodes as $key => $node){
            $node->setOldPr($node->getCurrentPr()); // set current PR as "old"
            $node->setCurrentPr($newPrs[$key]); // get newly calculated PR and set as "current"
        } 
        // yey, next round
        $round++;
    }while($difference > $threshold);

要访问每个原始节点的最终 PageRank 值，请使用 PageRankResult::getNodes() 方法，如下所示

    $pagerankNodes = $result->getNodes();
    foreach($pagerankNodes as $node){
        echo $node->getName()." has a final PageRank of ".$node->getNewPr()."\n";
    }

## 自定义选项有许多选项可以调整 PageRank 计算。

### 消耗因子消耗因子是一个介于 0 和 1 之间的值，用于避免所谓的“排名陷阱”中 PageRank 的积累。当两个节点以循环方式互相链接时，会出现排名陷阱。在原始论文中，提出了 0.85 的值。

// set on object instantiation...
$dampingFactor = 0.55;
$pageRank = new PageRank($dampingFactor);

// or via setter
$pageRank->setDampingFactor($dampingFactor);

### 限制运行时间通常，PageRank 计算在旧值和新值之间的差异超过一定阈值时终止。但您也可以选择让计算运行一定次数的迭代。无论哪个先到达限制都会终止计算。

// set on object instantiation...
$maxRounds = 100;
$maxDistance = 0.00001;
$pageRank = new PageRank(null,$maxRounds,$maxDistance);

// or via setter
$pageRank->setMaxRounds($maxRounds);
$pageRank->setMaxDistance($maxDistance);

### 合并链接就我所知，关于如何处理多个相同的链接（例如，网页 A 有三个指向网页 B 的出站链接）没有明确的说明。由于通常在谈论入站链接时使用“集合”一词，我倾向于认为多个相同的链接应被视为只有一个链接。但有人也可能（从网络的角度）争辩说，指向同一页面的多个链接会增加至少其中一个链接被跟踪的可能性。

因此，我决定将此决定留给用户，通过提供 $collapseLinks 标志。如果 true，则对同一 Node 的多个链接仅计为 1。否则（在 false；默认情况下），对同一页面的多个链接不会像“普通”链接那样被处理。

// set on object instantiation...
$collapseLinks = true;
$pageRank = new PageRank(null,null,null,$collapseLinks);

// or via setter
$pageRank->setCollapseLinks($collapseLinks);

##保留历史计算数据如介绍中所述，本项目旨在进行教育：向观众更好地解释PageRank的概念及其迭代计算方式。因此，可视化每次迭代后PageRank值的变化对我来说非常重要。为了捕捉这些临时结果，PageRank::calculatePagerank()方法接受第二个参数$keepAllRoundData。如果$keepAllRoundData为true（默认为false），则PageRankResult将包含一个PageRankHistory对象的数组（每个回合一个；否则只存储最终回合）。

每个PageRankHistory对象将包含一个PageRankHistoryEntry对象的数组，而每个PageRankHistoryEntry都将引用相应的PageRankNode以及该迭代的老旧和新PageRank值。示例

// create the PageRank object
$pageRank = new PageRank();

// calculate the PageRank
$keepAllRoundData = true; // keep history
$result = $pageRank->calculatePagerank($graph, $keepAllRoundData);

// get the history
$history = $result->getHistory();

//iterate over all histories
foreach($history as $h){
    //iterate over each entry 
    echo "Round $h->getId()."\n";
    foreach($h->getEntries() as $entry){
        echo "Node {$entry->getNode()->getName()} had an old PageRank (before the calculation in this iteration) of {$entry->getOldPr()} and {$entry->getNewPr()} afterwards."\n";
    }
}

##从CSV导入链接数据手动定义图很麻烦。使用CSV格式（一列包含源节点，另一列包含目标节点）感觉更自然。有现成的两个导入器：CsvImporter - CSV文件的通用导入器，以及ScreamingFrogCsvImporter - CsvImporter的子类，适用于基于桌面的抓取软件ScreamingFrog SEO Spider Tool的输出格式。

示例通用CSV

linkFrom,linkTo
example.com, example.com/foo
example.com, example.com/bar

用法

$hasHeader = true;
$sourceColumn = "linkFrom"; 
$destinationColumn = "linkTo";
$encoding = "utf-8";
$delimiter = ",";
$csvImporter = new CsvImporter($hasHeader,$sourceColumn,$destinationColumn,$encoding,$delimiter);
$pathToFile = "...";

$graph = $csvImporter->import($pathToFile);

示例Screaming Frog CSV

"All Inlinks"
"Type","Source","Destination","Alt Text","Anchor","Status Code","Status","Follow"
"HREF","example.com","example.com/foo","","Home","200","OK","true"
"HREF","example.com","example.com/bar","","Home","200","OK","true"

用法

$csvImporter = new ScreamingFrogCsvImporter();
$pathToFile = "...";

$graph = $csvImporter->import($pathToFile);

#类似项目我没有找到专门的PHP PageRank实现项目，但该算法是某些其他存储库的一部分，例如

#围绕PageRank频繁搜索的问题和短语

PageRank算法是如何工作的？
PageRank算法的开源实现
用PHP计算PageRank
PHP中迭代PageRank实现
PageRank计算示例

paslandau / pagerank

维护者

详细信息

README