Вместе с пакетом Python Network

Полную статью в блоге Sicara читайте здесь.

В этой статье показано, как выполнять обнаружение мошенничества с помощью анализа графиков. Благодаря алгоритму Персонализированный рейтинг страницы и пакету Python Networkx.

Обнаружение мошенничества - одна из основных сфер интересов науки о данных. Поскольку мошенничество - это редкое явление, основная задача - найти способ выявить ненормальное поведение. Вот почему анализ графиков является полезным методом для обнаружения мошенничества. Существует множество алгоритмов извлечения информации из графиков. В этой статье мы рассмотрим один из них: алгоритм персонализированного рейтинга страницы. Чтобы управлять нашими графиками и вычислять этот алгоритм, мы будем использовать пакет Python Networkx.

Алгоритм ранжирования страницы

Page Rank - это хорошо известный алгоритм, разработанный Ларри Пейджем и Сергеем Брином в 1996 году. Они учились в Стэндфордском университете, и это было частью исследовательского проекта по разработке нового типа поисковая система. Затем они успешно основали Google Inc..

Этот алгоритм присваивает числовой вес каждому узлу подключенной сети. Этот показатель представляет относительную важность узла в графе (его ранг).

Для вычисления Page Rank выполняется случайное блуждание. Это случайное блуждание определяется следующим образом:

  • Обходчик начинается со случайного узла на графике.
  • На каждой итерации ходунок следует по исходящей кромке к одному из следующих узлов с вероятностью α или перескакивает на другой случайный узел с вероятностью 1-α.

Теория PageRank утверждает, что воображаемый путешественник, который случайно переходит по ссылкам, в конце концов остановится. Вероятность на любом этапе того, что человек будет продолжать, называется коэффициентом демпфирования α.

Например, для Google сеть состоит из веб-сайтов, которые указывают друг на друга с помощью ссылок. Таким образом, мера рейтинга каждой веб-страницы - это вероятность того, что человек, случайно просматривающий Интернет, наконец, попадет на эту конкретную страницу.

С математической точки зрения, рейтинг страницы узла - это стационарная мера цепи Маркова, описываемая случайным блужданием.

На приведенной ниже анимации вы можете визуализировать случайное блуждание, выполняемое на связном графике с коэффициентом демпфирования, равным 0,85.

В приведенном выше примере можно было бы предсказать, что узел «c» имеет более высокий ранг. Это самый центральный узел. Напротив, узел «h», скорее всего, будет иметь низкий ранг.

Как вычислить рейтинг страницы с помощью Python и Networkx

Пакет python Networkx дает возможность выполнять анализ графов. В этом пакете реализовано множество алгоритмов (обнаружение сообщества, кластеризация…), pagerank - один из них.

С помощью приведенного ниже скрипта python, благодаря Networkx, мы сначала сгенерируем случайный график, а затем применим функцию pagerank.

Алгоритм персонализированного ранжирования страницы

Мы видели, что рейтинг страницы отражает важность узлов в сети. Персонализированный рейтинг страницы дает возможность выделить узлы на графике, которые являются центральными с точки зрения набора конкретных узлов.

…

Полную статью в блоге Sicara читайте здесь.