# Application of Graph Theory for Blockchain Technologies
## 5 Graph Theory Application in Blockchain Systems
### Analyzing Network Decentralization
#### 5.1.1 Mining Pool Power  
The mining landscape can be modeled as a dynamic graph with dominant pools occupying highly connected hub nodes as shown in Figure 1. Monitoring degree distribution skewness, betweenness centrality and the emergence of a few super-connected hubs can quantitatively track centralization among miners [66]. **Assumption 1**. :
* _Graph Model: The blockchain network is modeled as a dynamic graph_ \(G=(V,E)\)_, where_ \(V\) _represents the set of mining pools, and_ \(E\) _represents the connections between them._
* _Degree of a Node: The degree of a node_ \(d(v)\) _in_ \(G\) _represents the number of connections a mining pool has with other pools._
* _Wealth and Power Correlation: The mining power of a pool is directly proportional to its degree in the graph._
* _Network Growth: New nodes (mining pools) prefer to connect to existing nodes with higher degrees (a preferential attachment model, akin to the Barabasi-Albert model)._  
**Application Statement 1**. :
* _In a blockchain network modeled as a graph following the above assumptions, the network naturally evolves towards a state of increased centralization of mining power._  
**Proof. **  
1. Initial State Analysis:  
Let \(G_{0}\ =\ (V_{0},E_{0})\) be the initial state of the graph, where \(|V_{0}|\) is relatively large and the degree distribution \(D_{0}\ =\ \{d(v):v\in V_{0}\}\) is uniform or near-uniform. 2. Preferential Attachment:  
Define the attachment probability \(P_{\text{attach}}(v)\ =\ \frac{d(v)}{\sum_{v\in V}d(u)}\) for a new node connecting to an existing node \(v\). New nodes \(v_{\text{new}}\) prefer to attach to existing nodes \(v\) with higher \(P_{\text{attach}}(v)\). each new node is connected to \(k\) other ones, each one of those connections is chosen according to the \(P_{\text{attach}}\) probabilities
3. Degree Distribution Evolution:  
Over time, the degree distribution \(D_{t}\) for \(G_{t}\ =\ (V_{t},E_{t})\) becomes skewed, favoring nodes with initially higher degrees. The skewness can be represented by the increase in variance over time: \(\text{Var}(D_{t})>\text{Var}(D_{0})\) for \(t>0\). The variance could increase but still tend to a limit. It seems like the usual argument for the skewness of such a network is that the degree distribution follows a power law. It is indeed the case in the Barabasi-Albert model
4. Correlation of Degree and Mining Power:  
Let mining power \(M(v)\) of a node \(v\) be proportional to its degree: \(M(v)\propto d(v)\). Thus, \(M(v)\) is also increasingly skewed as \(D_{t}\) becomes skewed. 5. Centralization:  
Centralization can be quantified by a metric \(C(G_{t})\), where \(C(G_{t})\) increases as the skewness in \(M(v)\) increases. Formally, \(C(G_{t})>C(G_{0})\) for \(t>0\), indicating increased centralization over time. 6. Implications for Network Security and Decentralization:  
Security risk \(R(G_{t})\) and decentralization level \(\Delta(G_{t})\) can be formally defined. Increased \(C(G_{t})\) implies increased \(R(G_{t})\) and decreased \(\Delta(G_{t})\). Figure 1 graph is semi-randomly generated to illustrate the concept. In a real-world scenario, the nodes and edges would correspond to actual network participants and their interactions, which could be analyzed for decentralization aspects such as centralization risks, power distribution, or collaboration dynamics. Nodes represent entities within the network like mining pools, stakeholders, and developers. Edges signify the relationships or interactions between these entities. Node Color indicates the mining power of each node, which, for simplicity is assumed to be directly proportional to its degree. The color scale,  
from light to dark, illustrates the range of mining power across the network, with darker nodes possessing higher mining power. Node Size, corresponds to the degree of each node, with larger nodes having more connections. The size variation visually emphasizes the nodes that are more central to the network's structure, highlighting the preferential attachment growth model's impact.