# Graph algorithms

## Traditional Graph Analyticsβ

### Betweenness Centralityβ

Centrality analysis provides information about the nodeβs importance for an information flow or connectivity of the network. Betweenness centrality measures the extent to which a node lies on paths between other nodes in the graph.

### Biconnected Componentsβ

Biconnected components are parts of the graph important in the initial analysis. Finding biconnected components means finding a maximal biconnected subgraph.

### Bipartite Matchingβ

A bipartite graph is a graph in which we can divide vertices into two independent sets, such that every edge connects vertices between these sets. No connection can be established within the set. Matching in bipartite graphs (bipartite matching) is described as a set of edges that are picked in a way to not share an endpoint.

### Bridge Detectionβ

As in the real world, the definition of a bridge in graph theory denotes something that divides an entity into multiple components. Thus, more precisely, the bridge in graph theory denotes an edge that, when removed, divides the graph into two separate components. As the name suggests Bridge detection algorithm can be used to find bridges in graphs.

### Community Detectionβ

The notion of community in a graph represents similarly to what it represents in the real world. In graphs, community represents a partition of a graph, i.e., a set of nodes. There are several different ways to approach Community detection.

### Cycle Detectionβ

In graph theory, a cycle represents a path within the graph where only starting and ending nodes are similar. There are many implementations of Cycle detection. Cycles are not only popular in graph structures but also play an important role in number theory and cryptography.

### Graph Coloringβ

Certain applications require the special labeling of a graph called graph coloring. This βspecialβ labeling refers to the assignment of labels (which we call colors) in such a way that connected neighbors must not be given the same color.

### Katz Centralityβ

Katz Centrality is the measurement of centrality that incorporates the inbound path length starting from the wanted node. More central nodes will have closer connections rather than having many long-distance nodes connected to them.

### Maximum Flowβ

The Maximum Flow problem in optimization theory regards finding the maximum possible flow going through a flow network from source to sink nodes. A flow network, or a transportation network, is a directed graph with edge weights representing flow capacity.

### Node Similarityβ

The similarity of graph nodes is based on a comparison of adjacent nodes or the neighborhood structure. The result of this type of algorithm is always a pair of nodes and an assigned value indicating the match measure between them.

### PageRankβ

In the domain of centrality measurements, PageRank is arguably the most popular tool. Today, the most popular search engine in the world, Google, owes its popularity solely to this algorithm, developed in the early days by its founders.

### Union Findβ

By using a disjoint-set - a data structure that keeps track of non-overlapping sets, the algorithm enables the user to quickly check whether a pair of given nodes are in the same or different connected components. The implementation of the disjoint-set data structure and its operations uses the union by rank and path splitting optimizations.

## Streaming Graph Analyticsβ

### Dynamic Betweenness Centralityβ

MAGE includes a *fully dynamic* betweenness
centrality
computation tool that implements the
iCentral
^{1} algorithm. iCentral saves up on computation in two ways: it singles out the
nodes whose centrality scores could have changed and then incrementally updates
the scores, making use of previously calculated data structures where
applicable.

### Dynamic Katz Centralityβ

The online Katz centrality implementation results in a reduction of computations needed to update already calculated results. The algorithm offers substantially large speedups compared to static algorithm runs.

### Dynamic Community Detectionβ

To address the hidden relations among the nodes in the graph, especially those not connected directly, community detection can provide help. This familiar graph analytics method is being solved in various different ways.

### Dynamic Node2Vecβ

Dynamic Node2Vec is a random walk-based method that creates embeddings for every new node added to the graph. For every new edge, there is a recalculation of probabilities (weights) that are used in walk sampling.

### Dynamic PageRankβ

In the domain of estimating the importance of graph nodes, PageRank is arguably the most popular tool. Today, the most popular search engine in the world, Google, owes its popularity solely to this algorithm, developed in the early days by its founders. The need for its dynamic implementation arose at the moment when nodes and edges arrive in a short period of time.

## Machine Learning Graph Algorithmsβ

### Graph Neural Networks (GNN)β

Graph Neural Networks (GNN) are deep learning methods that can perform inference on data that is located in graphs.

### Graph Classificationβ

Graph classification allows you to analyze a graph as a whole. The structure and arrangement of nodes can reveal some hidden features in a graph. The main technique is to design features over the structure of the graph itself and then apply a classification algorithm.

### Graph Clusteringβ

In graph theory, Graph clustering is used to find subsets of similar nodes and group them together.

### Link Predictionβ

Link prediction is the process of predicting the probability of connecting the two nodes that were not previously connected in a graph. A wide range of different solutions can be applied to such a problem.

### Node Classificationβ

Prediction can be done at the node level. The basis of such prediction systems are features extracted from graph entities. Node classification uses node properties that exist on some nodes and then predicts them for nodes that don't have them.

### Node2Vecβ

Node2Vec is based on random walks. The point of this method is to map nodes that are most likely to be within a common random walk to the same place in n-dimensional space.

### Temporal Graph Networks (TGNs)β

Temporal Graph Networks are a type of graph neural network (GNN) for dynamic graphs. In recent years, GNNs have become very popular due to their ability to perform a wide variety of machine learning tasks on graphs, such as link prediction, node classification, and so on.