The importance of graph databases in data analysis cannot be overstated, and the recent development of subgraph computing is about to make them even more powerful. Although many people are already familiar with the idea behind graph computing, subgraph computing provides a new way of looking at things and greatly expands both what can be done with data as well as how it can be interpreted. In this post, we will introduce subgraph computing and explain its relevance to business.

# What is subgraph computing?
Subgraph computing is a term that is used when working with graph databases. In graph theory, a graph consists of vertices and edges connecting these vertices. A subgraph is any part of this full graph which includes some but not necessarily all of the nodes and/or edges from the main graph.

Subgraph computing is a specific kind of graph computing which deals with smaller, particular sections or 'subgraphs' within a bigger graph. This type of computing can be used to analyze and process specific areas of a network without having to process the entire graph, which can save time and computational resources. It's especially useful in large-scale data analysis where only certain parts of the data network are relevant for a particular analysis. For instance, in a social network, a subgraph could represent a group of people who are all friends with each other. Computing these subgraphs could give insights into the number of such tightly-knit friend groups in the network.

# What are the realistic use cases of subgraph computing?
- Social Network Analysis: Subgraph computing can be used to analyze specific communities or groups within a larger social network. For example, identifying subgroups of people with similar interests, behaviors, or connections.

- Recommendation Systems: In a recommendation network, nodes represent products and edges represent co-purchases. A subgraph may constitute a collection of merchandise which can be often bought collectively. Subgraph computing can help in analyzing user behavior within a specific context, and provide personalized recommendations based on that analysis.

- Fraud Detection: In a financial transaction network, nodes could represent individuals or entities, and edges could represent transactions. A subgraph might represent a suspicious pattern of transactions that often indicate fraudulent activity. By computing these subgraphs, a system could potentially identify and flag potential fraud cases.

- Bioinformatics: In organic networks, nodes can constitute proteins and edges can constitute interactions among them. A subgraph would possibly display a specific arrangement of proteins that form a practical complication. Analyzing those subgraphs can assist medical scientists aware of not unusual or massive protein complexes within the community.

- Network Security: In a pc community, nodes constitute devices like servers or routers, and edges represent connections. Subgraph computing can be used to identify and analyze specific parts of a network that are vulnerable to attacks or have already been compromised.

# Why does subgraph computing matter to commercial business?

In addition to the mentioned realistic use cases, subgraph computing brings business values to enterprises, including 

- Discovery of Patterns: Subgraph computing can help discover recurring patterns in complex networks. For instance, in attribution analysis, which is used in marketing to determine the most effective marketing channels, subgraphs could represent sequences of customer interactions leading to a purchase. Computing these subgraphs can help identify the most common or effective sequences.
- Anomaly Detection: In the context of capital flows, nodes could constitute debts and edges should constitute transactions. A subgraph may constitute a pattern of transactions that is indicative of cash laundering. By computing those subgraphs, you will become aware of anomalies and probably illicit activities.
- Predictive Analysis: Patterns found thru subgraph computing can also be used for predictive evaluation. For example, in a product recommendation community, styles of co-purchases can be used to expect future purchases.

# Comparison between graph computing and subgraph computing

While graph computing provides a wide assessment of a collection of graphs, which can be beneficial for knowledge of large-scale structures and tendencies, subgraph computing offers greater distinct and nearby information about the structure and properties of the graph. A user of graph databases would possibly need to depend on subgraphs to understand the structure of a complicated network, which includes the internet or a biological network. For instance, they may want to realize how many approaches a pandemic can spread via a network.

The two methods can be used to answer different types of questions. For example, if you're interested in understanding the overall structure of a set of data, graph computing might be more useful. If you're interested in finding patterns within a larger set of data, subgraph computing might be more useful.

In addition to providing more detailed and local information, subgraph computing offers better flexibility and efficiency for certain use cases.

- Flexibility: When dealing with large graphs, it's often impractical or unnecessary to query the whole graph.  For example, in case you're simply interested in a selected community inside a social community, you don't want to analyze the complete network. By focusing on subgraphs, you can isolate and analyze the relevant portions of the graph. This allows for more targeted analysis and reduces the amount of irrelevant data you have to deal with. In addition, it also allows for a more detailed analysis. For instance, by examining different subgraphs, you can identify local patterns or structures that may not be evident when looking at the graph as a whole.

- Efficiency: Subgraph computing is often more efficient than querying the whole graph. This is especially true for large graphs, where a full query can be computationally highly-priced and time-ingesting. By focusing on subgraphs, you can significantly reduce the computational load and speed up the analysis. This is not only more efficient, but it also means that the analysis can be more timely. In a rapidly changing network, a full graph query could be out of date by the time it's completed. Subgraph computing, on the other hand, can provide more up-to-date insights. Moreover, by reducing the computational load, subgraph computing also makes it possible to perform more in-depth analysis, such as running multiple queries or performing more complex computations.

As we wrap up, subgraph computing is more than just an extension of graph computing. It is an effective tool for reading complex networks and it can display crucial structures and styles that can be used for decision-making, prediction, and discovery. This transformative concept brings new intensity and measurement to data evaluation in graph databases. As we continue to discover its capacity, it's thrilling to imagine the effect it's going to have on the future of information analytics.

Subgraph computing is one of the key features that NebulaGraph Enterprise offers. If you’re interested in taking a trail, feel free to [reach out](https://www.nebula-graph.io/contact) to us.




Subgraph computing is a method of data analysis in graph databases that focuses on smaller, specific sections or 'subgraphs' within a larger graph, saving time and computational resources.

Subgraph Computing Uncovered: What It Is and Why It Matters


![How to compute the Betweenness Centrality against NebulaGraph](https://user-images.githubusercontent.com/90186547/146507685-97493119-3255-4429-ae2a-3d0ebeb616bf.jpg)

​Betweenness Centrality (BC for short) reflects the significance of vertices in the entire network. This article will introduce how to compute Betweenness Centrality against NebulaGraph.
   
# Relevant Concepts

**Centrality** represents how central a vertex is in the entire network graph, including Degree Centrality, Closeness Centrality, and Betweenness Centrality, etc. Degree Centrality reflects the popularity of a vertex by counting the number of its incoming and outgoing edges, while Closeness Centrality computes the sum of the length of the shortest paths between a vertex and all other vertices in the graph. Thus, the more central a vertex is, the closer it is to all other vertices.

**Betweenness Centrality** counts the number of times a vertex appears on the shortest path between any two other vertices, so as to represent the **significance** of this vertex to the network connectivity.

**The Betweenness Centrality** of a vertex is the proportion of the number of paths passing through this vertex in all the shortest paths to the total number of shortest paths.

**Calculating the Betweenness Centrality of a vertex in a graph can be conducted in a weighted graph or in an unweighted graph.** For unweighted graphs, Breadth-First Search (BFS for short) is used to find the shortest path, while for weighted graphs, Dijkstra’s algorithm is used.

The following algorithms are all targeted at undirected graphs.

# Applicable Scenarios

Betweenness Centrality reflects the significance of vertices in the entire network by measuring how a vertex bridges all other vertices in a graph or network. As we can see, Vertex C in the following figure acts as an important bridging vertex.

![How to compute the Betweenness Centrality against NebulaGraph](https://user-images.githubusercontent.com/90186547/146499037-22706464-9e30-456d-acca-cf5890b5957e.png)

**Betweenness Centrality** can be used to identify 

a. **The intermediary entities in anti-fraud scenarios** in the field of financial risk control.

b. **Specific disease control genes** in the medical field to improve drug targets.

# Betweenness Centrality Algorithm

The Betweenness Centrality of a vertex can be computed as follows:

$$C_B = \sum_{s{\not=} v {\not=} t \in V} \frac{\sigma_{st}(v)}{\sigma_{st}}$$

（Formula 1）

In this formula, 

$\sigma_{st}(v)$ is the number of shortest paths from `Vertex s` to `Vertex t`.

$\sigma_{st}$ is the number of shortest paths that pass through `Vertex v`.

`Vertex s` and `Vertex t` are a pair of vertices belonging to the vertex set.

To make it more convenient, the betweenness of each pair of vertices can be computed as:

$$\delta_{st}(v) = \frac{\sigma_{st}(v)}{\sigma_{st}}$$

（Formula 2）

So Formula 1 can be replaced by Formula 2, which gives rise to Formula 3 as follows:

$$C_B(v) = \sum_{s{\not=} v {\not=} t \in V} \delta_{st}(v)$$

（Formula 3）

# Solution Procedure

To get the Betweenness Centrality of `Vertex v`, namely to get $$\frac{, we need to know whether `Vertex v` lies on the path from `Vertex s` to `Vertex t`.

(1) To know whether `Vertex v` lies on the shortest path from `Vertex s` to `Vertex t`, use the following formula $d_G$ represents the shortest path from `Vertex s` to `Vertex t`):

If `Vertex v` lies on the shortest path from `Vertex s` to `Vertex t`, then $$d_G(s,t) = d_G(s,v) + d_G(v,t)$$ is satisfied.

（Formula 4）

$d_G(s,v)$ and $d_G(v,t)$ are mutually independent. According to the rules of combination, the total number of shortest paths from `Vertex s` to `Vertex t` is the product of the number of shortest paths from `Vertex s` to `Vertex t` and the number of shortest paths from `Vertex s` to `Vertex t`.

Based on the above two situations, Formula 5 can be inferred:

$$\sigma_{st}(v) = \begin{cases} 
                   \sigma_{sv} \times \sigma_{vt} &\text{if } d(s,v) + d(v,t) = d(s,t) \\
                   0 &\text{if } other                   
                   \end{cases}$$

（Formula 5）

（2）According to the above formula, we can get the conclusion that the number of shortest paths from `Vertex s` to `Vertex t` that pass through `Vertex w` is the result of

$\sigma_{st}(w) = \sigma_{sw} \times \sigma_{wt}$. In the graph, `Vertex v` is the preceding vertex of `Vertex w`. Therefore, the formula to count the number of shortest paths from `Vertex s` to `Vertex t` passing through `Vertex v` to `Vertex w` is:

$\sigma_{st}(v,\{v,w\}) = \sigma_{sv} \times \sigma_{wt}$ 

（Formula 6）

Here are two situations,  $$t = w$$ and $$t \not= w$$.

a. If $$t = w$$, then $$\sigma_{wt}$$ will not exist and we can get

$$\delta(v,\{v,w\}) = \frac{\sigma_{sv}}{\sigma_{sw}}$$ 

（Formula 7）

b. If $$t \not= w$$, then we can get

$$\delta(v,\{v,w\}) = \frac{\sigma_{sw}(v)}{\sigma_{sw}}  \times 
                       \frac{\sigma_{st}(w)}{\sigma_{st}} $$

（Formula 8）

(3) So considering the above two situations, we can get

$$\delta_s(v) = \sum_{w:v \in P_s(w)}(\frac{\sigma_{sw}(v)}{\sigma_{sw}} + \sum_{t \not= w \in V}\frac{\sigma_{sw}(v)}{\sigma_{sw}} \times \frac{\sigma_{st}(w)}{\sigma_{st}}) \\
= \sum_{w:v \in P_s(w)}\frac{\sigma_{sw}(v)}{\sigma_{sw}}(1 + \sum_{t \not= w \in V} \frac{\sigma_{st}(w)}{\sigma_{st}}) \\
= \sum_{w:v \in P_s(w)}\frac{\sigma_{sw}(v)}{\sigma_{sw}} (1 + \delta_s(w))
$$

（Formula 9）

In $$w:v \in P_s(w)$$, `Vertex v` is the predecessor of `Vertex w` in the path from `Vertex s` to `Vertex w`. 

(4) According to the above formula that gets the result of $\delta_{sv}$, the algorithm workflow of Betweenness Centrality in unweighted graphs can be given as follows:

![Solution Procedure](https://user-images.githubusercontent.com/90186547/146505278-7d5c8a71-b043-4369-8105-27257e200b59.png)

For unweighted graphs, follow the above process.

To calculate the Betweenness Centrality in weighted graphs requires Dijkstra's algorithm, that is, to change the code in the first while loop.

The Betweenness Centrality against NebulaGraph has achieved the algorithms for both weighted and unweighted graphs. For the code, see [https://github.com/vesoft-inc/nebula-algorithm/blob/master/nebula-algorithm/src/main/scala/com/vesoft/nebula/algorithm/lib/BetweennessCentralityAlgo.scala](https://github.com/vesoft-inc/nebula-algorithm/blob/master/nebula-algorithm/src/main/scala/com/vesoft/nebula/algorithm/lib/BetweennessCentralityAlgo.scala).

# Computation Examples

Firstly, read the graph data in NebulaGraph to specify the edge data for data reading.

Secondly, make a topological graph based on the edge data of NebulaGraph and perform centrality computation.

The graph data read in NebulaGraph can be illustrated in the following unweighted graph:

![Computation Examples](https://user-images.githubusercontent.com/90186547/146505643-38ddf9a1-5e9f-4339-b616-37336bb42cb8.png)

**Compute the BC of Vertex 1:**

| The vertex pair with the shortest path passing through Vertex 1 | The total number of shortest paths between the vertex pair | The number of the shortest path passing through Vertex 1 |
| --- | --- | --- |
| 2-4 | 3 （2-3-4, 2-5-4, 2-1-4）| 1 |
| The BC of Vertex 1:| 1/3 |  |

**Compute the BC of Vertex 2:**

| The vertex pair with the shortest path passing through Vertex 2 | The total number of shortest paths between the vertex pair | The number of the shortest path passing through Vertex 2|
| --- | --- | --- |
| 1-3 | 2 （1-2-3, 1-4-3）| 1 |
| 3-5 | 2（3-2-5, 3-4-5）| 1 |
| The BC of Vertex 2:| 1 |  |

**Compute the BC of Vertex 3:**

| The vertex pair with the shortest path passing through Vertex 3 | The total number of shortest paths between the vertex pair | The number of the shortest path passing through Vertex 3 |
| --- | --- | --- |
| 2-4 | 3 （2-3-4, 2-5-4, 2-1-4）| 1 |
| The BC of Vertex 3:| 1/3 |  |

**Compute the BC of Vertex 4:**

| The vertex pair with the shortest path passing through Vertex 4 | The total number of shortest paths between the vertex pair | The number of the shortest path passing through Vertex 4 |
| --- | --- | --- |
| 1-3 | 2 （1-4-3, 1-2-3） | 1 |
| 3-5 | 2（3-4-5, 3-2-5) | 1 |
| The BC of Vertex 4: | 1 |  |

**Compute the BC of Vertex 5:**

| The vertex pair with the shortest path passing through Vertex 5 | The total number of shortest paths between the vertex pairs | The number of the shortest path passing through Vertex 5 |
| --- | --- | --- |
| 2-4 | 3 （2-3-4, 2-5-4, 2-1-4） | 1 |
| The BC of Vertex 5: | 1/3 |  |

Therefore, the BC of each vertex is: Vertex 1: 1/3 Vertex 2: 1 Vertex 3: 1/3 Vertex 4: 1 Vertex 5: 1/3

# Result Examples

Data: Read the edge data in the NebulaGraph test, and take srcId, dstId, and rank as the triplet of edges in the topological graph (Source Vertex, Destination Vertex, and Rank).

```shell
(root@nebula) [test]> match (v:node) -[e:relation] -> ()  return e
+------------------------------------+
| e                                  |
+------------------------------------+
| [:relation "3"->"4" @1 {col: "f"}] |
+------------------------------------+
| [:relation "2"->"3" @2 {col: "d"}] |
+------------------------------------+
| [:relation "2"->"5" @4 {col: "e"}] |
+------------------------------------+
| [:relation "4"->"5" @2 {col: "g"}] |
+------------------------------------+
| [:relation "1"->"5" @1 {col: "a"}] |
+------------------------------------+
| [:relation "1"->"2" @3 {col: "b"}] |
+------------------------------------+
| [:relation "1"->"4" @5 {col: "c"}] |
+------------------------------------+
```

Read the edge data in NebulaGraph, set the graph as unweighted, and calculate the Betweenness Centrality of each vertex. The results are as follows:

```shell
vid: 4 BC: 1.0
vid: 1 BC: 0.3333333333333333
vid: 3 BC: 0.3333333333333333
vid: 5 BC: 0.3333333333333333
vid: 2 BC: 1.0
```

Read the edge data of NebulaGraph, set the graph as weighted, and calculate the Betweenness Centrality of each vertex. The results are as follows:

```shell
vid: 4 BC: 2.0
vid: 1 BC: 0.5
vid: 3 BC: 1.0
vid: 5 BC: 2.0
vid: 2 BC: 0.0
```

# References

- Paper: A Faster Algorithm for Betweenness Centrality
- The source code of Python's NetworkX realizing Betweenness Centrality: [https://github.com/networkx/networkx/blob/master/networkx/algorithms/centrality](https://github.com/networkx/networkx/blob/master/networkx/algorithms/centrality)

Join our [Slack channel](https://join.slack.com/t/nebulagraph/shared_invite/zt-7ybejuqa-NCZBroh~PCh66d9kOQj45g) if you want to discuss with the rest of the [NebulaGraph](https://www.nebula-graph.io/) community!

Betweenness Centrality (BC for short) reflects the significance of vertices in the entire network. This article will introduce how to compute Betweenness Centrality against NebulaGraph.

Tag