<style>

html, body, .ui-content {
background-color: #222121;
color: #ddd;
}

::selection {
background-color: #d46b95;
color: black;
}

.markdown-body:not(.next-editor) pre {
padding: 16px;
background-color: #353535;
color: #e0def4;
}
.markdown-body:not(.next-editor) strong {
color: #d46b95;
}
.markdown-body:not(.next-editor) em {
color: #fbaa77;
}
.markdown-body:not(.next-editor) code {
color: #eee;
background-color: #353535;
}
.markdown-body h1,
.markdown-body h2,
.markdown-body h3,
.markdown-body h4,
.markdown-body h5,
.markdown-body h6 {
color: #dfdad9;

}

.markdown-body h1:hover,
.markdown-body h2:hover,
.markdown-body h3:hover,
.markdown-body h4:hover,
.markdown-body h5:hover,
.markdown-body h6:hover {
color: #ffff90;
}

.markdown-body hr {
height: 0em;
padding: 0;
margin: 24px 0;
background-color: #212121;
border: 0;
border-top: 3px dashed #8c8b8b;
}

pre {
background-color:#353535;

}

code {
background-color:#353535
}

.hljs-keyword {
color: #ffaacc;
}

.hljs-type {
color: #9ccfd8
}
.hljs-number {
color: #fbaa77
}

.hljs-operator {
color: #fbea77
}

.hljs-string {
color: #a3be8c
}

.hljs-built_in {
color: #fbea77
}

.markdown-body h1,
.markdown-body h2 {
border-bottom-color: #ffffff69;
}

.markdown-body h1 .octicon-link,
.markdown-body h2 .octicon-link,
.markdown-body h3 .octicon-link,i
.markdown-body h4 .octicon-link,
.markdown-body h5 .octicon-link,
.markdown-body h6 .octicon-link {
color: #fff;
}

.markdown-body img {
background-color: transparent;
}

.ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a {
color: white;
border-left: 2px solid white;
}

.expand-toggle:hover,
.expand-toggle:focus,
.back-to-top:hover,
.back-to-top:focus,
.go-to-bottom:hover,
.go-to-bottom:focus {
color: white;
}

.ui-toc-dropdown {
background-color: #212121;
}

.ui-toc-label.btn {
background-color: #191919;
color: white;
}

.ui-toc-dropdown .nav>li>a:focus,
.ui-toc-dropdown .nav>li>a:hover {
color: white;
border-left: 1px solid white;
}

.markdown-body blockquote {
color: #bcbcbc;
}

.markdown-body table tr {
background-color: #5f5f5f;
}

.markdown-body table tr:nth-child(2n) {
background-color: #4f4f4f;
}

.markdown-body code,
.markdown-body tt {
color: #eee;
background-color: rgba(230, 230, 230, 0.36);
}

a,
.open-files-container li.selected a {
color: #5EB7E0;
}

</style>
# Unit 1 Graph Theory

## Rooted Trees Formulae

# Unit 2 Graph Theory

## Chromatic Polynomial

### Product Rule

### Path Polynomial

### **Decomposition Theorem**

### **Multiplication Theorem**

## Matching and Coverings




# Unit 3 Graph Theory

## All Centrality Measures

| Centrality Measure | Formula (Summation Form) | Alternate Form |
|-----------------------------|------------------------------------------------------------|------------------------------------------------------------|
| **Degree Centrality** | $C_d(v) = \frac{\text{d}_i}{n-1}$ | |
| **Degree Centrality (sum)** | $C_{d,\text{sum}}(v) = \frac{\text{d}_i}{\sum_{i}{d_i}}$ | $C_{d,\text{sum}}(v) = \frac{\text{d}_i}{2\|E\|}$ |
| **Degree Centrality (max)** | $C_{d,\text{max}}(v) = \frac{\text{degree}(v)}{\max \text{degree}(u)}$ | |
| **Betweenness Centrality** | $C_b(v) = \sum_{s\neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$ | |
| | $C_{b,\text{normalized}}(v) = \frac{C_b(v)}{(N-1)(N-2)}$ | |
| **Closeness Centrality** | $C_c(v) = \frac{1}{\sum_{u} l(i, j)}$ | |
| | $C_{c,\text{normalized}}(v) = \frac{N-1}{\sum_{u} l(i, j)}$ | |
| **Eigenvector Centrality** | $C_e(V_i) = \frac{\sum_{j} A_{j,i}C_e(V_j)}{\lambda}$ | $\mathbf{C}_e = \frac{1}{\lambda}\mathbf{A^T C}_e$ |
| | | |
| **Katz Centrality** | $C_k(V_i) =\alpha \sum_{j} A_{j,i}C_k(j) + \beta$ | $\mathbf{C}_k =\beta(\mathbf{I} - \alpha\mathbf{A^T})*\mathbf{1}$ |
| | | |
| **Pagerank Centrality** | $C_p(V_i) = \alpha\sum_{j} \frac{A_{j,i}C_p(j)}{\text{d}^{out}_{u}} + \beta$| $\mathbf{C}_p = \beta(\mathbf{I} + \alpha\mathbf{AD}^{-1})^{-1}*\mathbf{1}$ |

## Important Definitions
### Small World Networks

Characterized by high clustering and short average path lengths, enabling efficient information transfer. Example: "six degrees of separation" phenomenon (Mildreds Experiment) .

### Scale-Free Networks

Exhibit a power-law distribution of node degrees, with a few highly connected hubs and many nodes with few connections. Examples: social networks, World Wide Web, biological networks.

### Homophily

The tendency of individuals to connect with others who share similar characteristics or interests. Influences social network structure and information flow.

### **Network Cohesion Parameters**

### Density
- **Definition:** Density measures the proportion of actual connections to possible connections in a network. It is calculated as the ratio of the number of edges to the total possible number of edges.
- **Significance:** High density indicates strong connectivity within the network.

### Diameter
- **Definition:** The diameter of a network is the longest shortest path between any pair of nodes. It represents the maximum number of edges that must be traversed to go from one node to another.
- **Significance:** A smaller diameter suggests shorter paths and potentially quicker communication.

### Average Path Length
- **Definition:** The average path length is the average number of edges along the shortest paths for all pairs of nodes in the network.
- **Significance:** Smaller average path length implies efficient information transfer.

### Entropy of Degree Probability
- **Definition:** Entropy measures the uncertainty or randomness in the distribution of node degrees. In the context of degree distribution, it quantifies how evenly degrees are distributed across nodes.
- **Significance:** Higher entropy indicates a more diverse degree distribution.

### **Assortativity**

- **Definition:** Assortativity measures the preference of nodes to connect with others that have a similar degree. Positive assortativity means nodes tend to connect to nodes of similar degree, while negative assortativity indicates connections between nodes of different degrees.

### **Rich Club Coefficient**

- **Definition:** The rich club coefficient measures the extent to which high-degree nodes are more densely interconnected with each other than expected by chance.
- **Significance:** A high rich club coefficient suggests the presence of a richly interconnected core of high-degree nodes in the network.

## Local Clustering Coefficient

- **Formula:**
$$
C_i = \frac{2E_i}{k_i(k_i-1)}
$$

- **Explanation:**
- $C_i$ represents the local clustering coefficient of node $i$.
- $E_i$ is the number of edges between the neighbors of node $i$.
- $k_i$ is the degree of node $i$.

- **Significance:**
- Local clustering coefficient measures the proportion of actual connections among the neighbors of a node compared to the total possible connections. It indicates how well-connected the immediate neighbors of a node are.

## Global Clustering Coefficient

- **Formula:**
$$
C = \frac{3 \times \text{number of triangles}}{\text{number of connected triples}}
$$

- **Explanation:**
- $C$ represents the global clustering coefficient for the entire network.
- A connected triple consists of three nodes where at least two edges exist.
- The global clustering coefficient considers all connected triples and counts the number of triangles in the network.

- **Significance:**
- Global clustering coefficient measures the overall tendency of nodes to form triangles in the network. It provides a sense of the network's overall clustering structure.


# Unit 4
## Girvan-Newman Algorithm

- **Explanation:**
- **Objective:** The Girvan-Newman algorithm focuses on detecting community structures by iteratively removing edges with the highest betweenness centrality.
- **Steps:**
1. Calculate the betweenness centrality of all edges in the network.
2. Remove the edge with the highest betweenness centrality.
3. Recalculate betweenness centrality after each removal.
4. Repeat steps 2-3 until the desired number of communities is achieved or the network is fully disconnected.
- **Significance:** The algorithm identifies communities by targeting edges that act as bridges between different parts of the network.

## Louvain Method

- **Explanation:**
- **Objective:** The Louvain method is a greedy optimization algorithm for community detection, aiming to maximize the modularity of the network.
- **Steps:**
1. Assign each node to its own community.
2. Iterate through each node and move it to the neighboring community that maximizes the gain in modularity.
3. Merge communities and repeat until modularity cannot be improved further.
- **Significance:** Louvain efficiently identifies communities by optimizing the modularity metric, capturing the strength of community structure.

## Clique Percolation Method

- **Explanation:**
- **Objective:** The Clique Percolation Method identifies communities based on the percolation of overlapping cliques.
- **Steps:**
1. Identify all cliques (fully connected subgroups) of a given size in the network.
2. Create a binary matrix indicating which nodes are part of each clique.
3. Define communities based on the percolation of cliques, where nodes sharing a sufficient number of cliques are considered part of the same community.
- **Significance:** This method allows for overlapping communities and captures structures formed by shared cliques.