What people are saying about graph algorithms and the value it brings. In this post, graph algorithms will be discussed.
What are Graph Algorithms?
Graph models deal with a lot of data. Graph data is analyzed to draw useful information to identify human interactions. This enables the discovery of new business insights and opportunities
There are three kinds of algorithms; graph traversal, centrality, clustering. Graph traversal is the process of visiting each vertex in a graph. Centrality identifies the most important vertices within a graph. Graph cluster identifies a group of vertices which are connected in a particular way. For example, let’s look at the followings:
1. Graph Traversal
Finding the shortest path
Find a path between two vertices in a graph whose sum of the weights of its edges is minimized. There are many algorithms to solve this problem: Dikstra, A*, Bellman-Ford, Floyd-Warshall, etc.
▲ Feature 1. Shortest path between vertices A and F (pic from wikipedia.org)
E(v) of vertex v is the greatest distance between v and any other vertex.
r of a graph is the minimum eccentricity of any vertex.
d of a graph is the maximum eccentricity of any vertex.
▲ Feature 2. Graph distance
The farness is sum of its distances from all other nodes. The closeness is the reciprocal of the farness.
The number of times a node acts and a bridge along the shortest path between two other nodes.
The number of direct neighbors
The relative scores to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes.
▲ Feature 3. Pagerank is a variant of the eigenvector centrality measure (pic from wikipedia.org)
Finding Maximal cliques in an undirected graph.
Clique is a subset of vertices of an undirected graph. Every two distinct vertices in the clique are adjacent.
▲ Feature 4. The 11 light blue triangles form maximal cliques. The two dark blue 4-cliques are both maximum and maximal, and the clique number of the graph is 4 (pic from wikipedia.org)
- Connected components
Undirected subgraph in which any two vertices are connected each other.
Strongly connected components.
Connect components in directed graph.
BITNINE GLOBAL INC., THE COMPANY SPECIALIZING IN GRAPH DATABASE
비트나인, 그래프 데이터베이스 전문 기업