Я пытаюсь реализовать алгоритм page rank.
У меня всего 5 веб-страниц (см. Изображение ниже).Следующее изображение представляет график и показывает, какая веб-страница содержит ссылки на какую страницу.
Я сохранил эту связь веб-страниц в HashMap таким образом, чтобы уникальная ссылка каждой веб-страницы сохранялась как keyи HashSet, содержащий все ссылки на веб-страницы, на которые указывает данная веб-страница, сохраняется как значение этого ключа.(см. изображение ниже)
Каждая веб-страница представлена своей уникальной ссылкой.Вышеупомянутый HashMap представлен в коде как
HashMap<URI, HashSet<URI>> graph = new HashMap<>();
Я выбрал значение decay, равное 0.85 и epsilon, равное 0.00001
Проблема
После генерации вышеупомянутого Hashmap я вычисляю page rank каждой веб-страницы.
Конечные ранги конвергированных страниц должны составлять
но мои фактические ранги страниц:
Page A = 0.3170604814815385
Page B = 0.18719407056490575
Page C = 0.13199010955519944
Page D = 0.31131469834360015
Page E = 0.05244064005475638
Фактические значения для каждой страницы в порядке, так как разница между фактическим и ожидаемым значением для каждой страницы меньшевыбранное epsilon значение за исключением Page D.
Я пробовал разные входы для этого алгоритма page rank, независимо от того, что я пробую, у меня всегда естьодна или две веб-страницы , для которых значения ранга страницы не верны .Алгоритм возвращается до того, как все страницы сошлись в разрядах, то есть разница между старыми и новыми разрядами для каждой страницы меньше epsilon значения.
Вопрос
Чтоя делаю не так?Почему мой алгоритм ранжирования страниц возвращает ранги страниц до того, как все они сойдутся?
Код
Следующая функция генерирует HashMap, показанное на изображениях выше.
private static HashMap<URI, HashSet<URI>> makeGraph(HashSet<WebPage> webpages) {
HashMap<URI, HashSet<URI>> webPagesGraph = new HashMap<>();
HashSet<URI> singleWebPageLinks;
HashSet<URI> availableWebPages = new HashSet<>();
// add all the web pages available in data set in a collection
for (WebPage doc : webpages) {
availableWebPages.add(doc.getUri());
}
for (WebPage doc : webpages) {
singleWebPageLinks = new HashSet<>();
for (URI link : doc.getLinks()) {
// if link is not pointing to the web page itself and is available in data set
if (!link.equals(doc.getUri()) && availableWebPages.contains(link)) {
singleWebPageLinks.add(link);
}
}
webPagesGraph.put(doc.getUri(), singleWebPageLinks);
}
return webPagesGraph;
}
Следующая функция вычисляет ранги страниц
private static HashMap<URI, Double> makePageRanks(HashMap<URI, HashSet<URI>> graph,
double decay,
int limit,
double epsilon) {
// Step 1: The initialize step should go here
HashMap<URI, Double> oldPageRanks = new HashMap<>();
HashMap<URI, Double> newPageRanks = new HashMap<>();
double singleWebPageNewRank;
int numLinkedPagesBySinglePage;
double singleWebPageOldRank;
boolean haveConverged = true;
double rank;
// provide ranks to each web page
// initially the rank given to each page is 1/(total no. of web pages).
// also give new page rank to each page equal to zero
for (URI key : graph.keySet()) {
oldPageRanks.put(key, (double) 1 / graph.size());
newPageRanks.put(key, 0.0);
}
for (int i = 0; i < limit; i++) {
// Step 2: The update step should go here
for (URI uri : graph.keySet()) {
singleWebPageOldRank = oldPageRanks.get(uri);
numLinkedPagesBySinglePage = graph.get(uri).size();
// if any web page doesn't have any outgoing links to any other
// web page, increase the new page rank for every web page
if (numLinkedPagesBySinglePage == 0) {
for (URI u : newPageRanks.keySet()) {
singleWebPageNewRank = decay * (singleWebPageOldRank / graph.size());
saveNewRank(newPageRanks, u, singleWebPageNewRank);
}
} // increase the new page rank of every web page that is pointed to
// by current web page
else {
for (URI linkedWebPageURI : graph.get(uri)) {
singleWebPageNewRank = decay * (singleWebPageOldRank / numLinkedPagesBySinglePage);
saveNewRank(newPageRanks, linkedWebPageURI, singleWebPageNewRank);
}
}
}
// account for random user/surfer by adding (1 - decay) / (total no. of web pages)
// to each web page's new rank
for (URI uri : newPageRanks.keySet()) {
rank = newPageRanks.get(uri);
rank = rank + ((1 - decay) / graph.size());
newPageRanks.put(uri, rank);
// check for convergence
// check if difference b/w old rand and new rank for each web page
// is less than epsilon or not
// if difference between old and new ranks is greater than or
// equal to epsilon even for one web page, ranks haven't converged
if (oldPageRanks.get(uri) - newPageRanks.get(uri) >= epsilon) {
haveConverged = false;
}
}
if (haveConverged) {
return oldPageRanks;
} else {
haveConverged = true;
overWriteOldRanksWithNewRanks(oldPageRanks, newPageRanks);
}
}
return oldPageRanks;
}
Следующие две функции являются служебными функциями, которые вызываются из makePageRanks function
// save the new page rank for a given web page by adding the passed new page rank to
// its previously saved page rank and then saving the new rank
private static void saveNewRank(HashMap<URI, Double> newPageRanks, URI pageURI, double pageNewRank) {
pageNewRank += newPageRanks.get(pageURI);
newPageRanks.put(pageURI, pageNewRank);
}
// overwrite old page ranks for next iteration
private static void overWriteOldRanksWithNewRanks(HashMap<URI, Double> oldRanks, HashMap<URI, Double> newRanks) {
for (URI key : newRanks.keySet()) {
oldRanks.put(key, newRanks.get(key));
// make new rank for each web page equal to zero before next iteration
newRanks.put(key, 0.0);
}
}
Ниже приведен простой класс WebPage
public class WebPage {
private ArrayList<String> words;
private URI uri;
private ArrayList<URI> links;
WebPage(URI uri, ArrayList<String> words, ArrayList<URI> links) {
this.words = words;
this.uri = uri;
this.links = links;
}
public ArrayList<String> getWords() {
return words;
}
public URI getUri() {
return uri;
}
public ArrayList<URI> getLinks() {
return links;
}
}
и, наконец, метод main для всех, кто хочет посмотреть, какой вклад я даю в алгоритм ранжирования страниц
public static void main(String[] args) {
ArrayList<URI> pageALinks = new ArrayList<>();
pageALinks.add(createURI("www.b.com"));
pageALinks.add(createURI("www.d.com"));
URI pageAURI = createURI("www.a.com");
WebPage pageA = new WebPage(pageAURI, new ArrayList<>(), pageALinks);
ArrayList<URI> pageBLinks = new ArrayList<>();
pageBLinks.add(createURI("www.c.com"));
pageBLinks.add(createURI("www.d.com"));
URI pageBURI = createURI("www.b.com");
WebPage pageB = new WebPage(pageBURI, new ArrayList<>(), pageBLinks);
ArrayList<URI> pageCLinks = new ArrayList<>();
URI pageCURI = createURI("www.c.com");
WebPage pageC = new WebPage(pageCURI, new ArrayList<>(), pageCLinks);
ArrayList<URI> pageDLinks = new ArrayList<>();
pageDLinks.add(createURI("www.a.com"));
URI pageDURI = createURI("www.d.com");
WebPage pageD = new WebPage(pageDURI, new ArrayList<>(), pageDLinks);
ArrayList<URI> pageELinks = new ArrayList<>();
pageELinks.add(createURI("www.d.com"));
URI pageEURI = createURI("www.e.com");
WebPage pageE = new WebPage(pageEURI, new ArrayList<>(), pageELinks);
HashSet<WebPage> pages = new HashSet<>();
pages.add(pageA);
pages.add(pageB);
pages.add(pageC);
pages.add(pageD);
pages.add(pageE);
HashMap<URI, HashSet<URI>> graph = makeGraph(pages);
HashMap<URI, Double> map = makePageRanks(graph, 0.85, 100, 0.00001);
}