# Application of Graph Theory for Blockchain Technologies
## 5 Graph Theory Application in Blockchain Systems
### Analyzing Network Decentralization
#### 5.1.2 Stake Pool Power  
For proof-of-stake consensus, the graph analysis of delegate nodes and their stake ratios determine the relative influences of validator pools and the likelihood of collusion. Figure 3 graph illustrates the concept of staking delegations in a proof-of-stake blockchain network [67]. In an actual blockchain network, these edges would represent real staking delegations from one pool to another, and their analysis could reveal patterns of stake distribution, possible centralization of power, and the overall structure of the stake delegation network. Nodes represent stake pools. Directed edges (arrows) represent staking delegations between pools.  
**Assumption 2**.:
* _Graph Model: The blockchain network is modeled as a (weighted) directed graph_ \(G~{}=~{}(V,E)\)_, where each node_ \(v\in V\) _represents a stake pool and each arc_ \((u,v)\in E\) _represents staking delegation from pool_ \(u\) _to pool_ \(v\)_._
* _Stake Representation: The weight of each node_ \(w(v)\) _corresponds to the total stake delegated to the pool_ \(v\)_._
* _Influence by Stake: The influence or power of a stake pool is directly proportional to its total stake._
* _Network Dynamics: New stakeholders tend to delegate their stake to pools with higher existing stakes, modeling a preferential attachment similar to the Barabasi-Albert model._  
**Application Statement 2**.:
* _In a blockchain network modeled as a directed graph following the above assumptions, the network evolves towards a state where a small number of stake pools accumulate a disproportionately large amount of total stake, indicating a trend towards centralization of stake power._  
**Proof.**  
1. Initial State Analysis: Let \(G_{0}~{}=~{}(V_{0},E_{0})\) represent the initial state of the graph, with \(w(v_{0})\) denoting the stake for each pool \(v_{0}\in V_{0}\), where \(w(v_{0})\) is relatively uniform across \(V_{0}\).
2. Preferential Attachment Dynamics: Define \(P_{\text{delegate}}(v)~{}=~{}\frac{w(v)}{\sum_{w\in V}w(u)}\), the probability of a new stakeholder delegating their stake to pool \(v\). New stakeholders are more likely to delegate to pools with higher \(w(v)\), following preferential attachment.
3. Evolution of Stake Distribution: As time progresses, this dynamic leads to an evolved graph \(G_{t}~{}=~{}(V_{t},E_{t})\) at time \(t\), where the distribution of \(w(v)\) for \(v\in V_{t}\) becomes increasingly skewed. This skewness is represented by an increasing variance: \(\text{Var}(w(V_{t}))>\text{Var}(w(V_{0}))\) for \(t>0\).
4. Centralization of Stake Power: Quantify centralization at time \(t\) with \(C_{\text{stake}}(G_{t})\), which increases with the skewness of \(w(v)\). Formally, \(C_{\text{stake}}(G_{t})>C_{\text{stake}}(G_{0})\) for \(t>0\), indicating a trend towards increased centralization of stake power.  
In Figure 3, the Node Color represents the influence score of each stake pool, with the color scale indicating the level of influence based on both the stake and the pool's position within the network's structure. Lighter colors denote higher influence scores. Node Size, corresponds to the total stake of each pool, allowing for a direct visual comparison between a pool's stake and its overall influence within the network. Color Bar (Influence Score),aids in interpreting the influence scores, with the gradient showing the range of influence scores across the network from low to high.  
This proof demonstrates that under the given assumptions and network dynamics, a blockchain network's stake distribution evolves towards increased centralization, with a few stake pools gaining a majority of the total stake. This centralization of stake power can have implications on the network's security and governance, potentially contradicting the decentralized ethos of blockchain technology.