Поскольку я сейчас провожу большую часть своего времени в окружении графиков, я подумал, что было бы интересно узнать немного больше об обработке графиков , о чем мой коллега Джим написал пару лет назад.
Мне нравится думать, что типы запросов, которые вы делаете с механизмом обработки графиков, похожи на глобальные запросы стилей графов, где вы принимаете во внимание большинство узлов в графике и выполняете какие-то вычисления.
Один из интересных глобальных алгоритмов графа, с которыми я недавно столкнулся, — это « центральность между », которая позволяет нам определить центральность каждого узла по отношению к остальной части сети / графа.
[Междуцентричность] равна количеству кратчайших путей от всех вершин ко всем остальным, которые проходят через этот узел. Центральность промежуточности является более полезной мерой (чем просто связность) как нагрузки, так и важности узла. Первый является более глобальным для сети, а второй — только локальный эффект.
Я хотел найти библиотеку, с которой я мог бы поиграть, чтобы лучше понять, как работает этот алгоритм, и я наткнулся на graphstream, который, похоже, выполняет свою работу.
Я смог начать работу, создав файл pom Maven со следующими зависимостями:
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<packaging>jar</packaging>
<artifactId>my-gs-project</artifactId>
<groupId>org.graphstream</groupId>
<version>1.0-SNAPSHOT</version>
<name>my-gs-project</name>
<description/>
<dependencies>
<dependency>
<groupId>org.graphstream</groupId>
<artifactId>gs-core</artifactId>
<version>1.0</version>
</dependency>
<dependency>
<groupId>org.graphstream</groupId>
<artifactId>gs-algo</artifactId>
<version>1.0</version>
</dependency>
</dependencies>
</project>
Я хотел найти работающий пример, который мог бы использовать, чтобы понять, как рассчитывается центральность межличности, и я нашел один на слайде 14 этих лекционных заметок из Университета Невады.
Пример графика выглядит следующим образом:
И чтобы выяснить центральность промежуточности, нам нужно взять каждую пару узлов и посмотреть, через какие (если они есть) узлы должен пройти путь между ними.
A -> B: None A -> C: B A -> D: B, C A -> E: B, C, D B -> C: None B -> D: C B -> E: C, D C -> D: None C -> E: D D -> E: None
Таким образом, для этого примера мы получаем следующие значения центральности для каждого узла:
A: 0 B: 3 C: 4 D: 3 E: 0
Если мы пропустим это через поток графа, то увидим, что значения удваиваются, потому что он считает пары дважды (например, A-> B отличается от B-> A):
public class Spike {
public static void main(String[] args) {
Graph graph = new SingleGraph("Tutorial 1");
Node A = graph.addNode("A");
Node B = graph.addNode("B");
Node E = graph.addNode("E");
Node C = graph.addNode("C");
Node D = graph.addNode("D");
graph.addEdge("AB", "A", "B");
graph.addEdge("BC", "B", "C");
graph.addEdge("CD", "C", "D");
graph.addEdge("DE", "D", "E");
BetweennessCentrality bcb = new BetweennessCentrality();
bcb.init(graph);
bcb.compute();
System.out.println("A="+ A.getAttribute("Cb"));
System.out.println("B="+ B.getAttribute("Cb"));
System.out.println("C="+ C.getAttribute("Cb"));
System.out.println("D="+ D.getAttribute("Cb"));
System.out.println("E="+ E.getAttribute("Cb"));
}
}
A=0.0 B=6.0 C=8.0 D=6.0 E=0.0
Из этого вычисления мы можем узнать, что в этом графе узел «C» является наиболее влиятельным, потому что большинство путей между другими узлами должны проходить через него. В этом не так много, поскольку узлы «B» и «D» находятся близко друг к другу.
Теперь, когда я лучше понял, как выполнить алгоритм вручную, я подумал, что должен попытаться выяснить, что вернет пример из документации .
Пример графика выглядит следующим образом:
И пути между узлами будут следующими:
Поскольку я знаю, что graphstream рассматривает график как ненаправленный, я не уважаю направление отношений в этом расчете)
A -> B: None A -> C: B A -> D: E A -> E: None B -> C: None B -> D: E or C B -> E: None C -> D: None C -> E: D or B D -> E: None
Для некоторых из них было два потенциальных пути, поэтому мы даем 1/2 балла каждому узлу, что приводит к этим общим
A: 0 B: 1.5 C: 0.5 D: 0.5 E: 1.5
Если мы запустим это через graphstream, мы ожидаем, что значения удвоятся для каждого узла:
public class Spike {
public static void main(String[] args) {
Graph graph = new SingleGraph("Tutorial 1");
Node A = graph.addNode("A");
Node B = graph.addNode("B");
Node E = graph.addNode("E");
Node C = graph.addNode("C");
Node D = graph.addNode("D");
graph.addEdge("AB", "A", "B");
graph.addEdge("BE", "B", "E");
graph.addEdge("BC", "B", "C");
graph.addEdge("ED", "E", "D");
graph.addEdge("CD", "C", "D");
graph.addEdge("AE", "A", "E");
BetweennessCentrality bcb = new BetweennessCentrality();
bcb.init(graph);
bcb.compute();
System.out.println("A="+ A.getAttribute("Cb"));
System.out.println("B="+ B.getAttribute("Cb"));
System.out.println("C="+ C.getAttribute("Cb"));
System.out.println("D="+ D.getAttribute("Cb"));
System.out.println("E="+ E.getAttribute("Cb"));
}
}
A=0.0 B=3.0 C=1.0 D=1.0 E=3.0
Эта библиотека работает для некоторого определения центральности промежуточности, но в идеале я хотел бы принять во внимание направление отношений, так что я собираюсь попробовать его с одной из других библиотек, с которыми я сталкивался.
Пока что я знаю о других библиотеках обработки графиков, таких как graphchi , JUNG , Green-Marl и giraph, но если вы знаете какие-либо другие, которые я должен попробовать, пожалуйста, дайте мне знать.