## Connected Components In an [[Network Types#^d09159|Undirected Graph]], a connected component is a subset of nodes $V^\prime \subset V$, where - A [[Network Types#^7075f3|Walk]] between any two nodes $v_i, v_j \in V^\prime$ exists. - The component is maximally connected, which means the addition of any other node would violate this property. In directed graphs we distinguish between “strongly connected” and “weakly connected graphs”. - *Weakly connected component:* Acting as if the graph would be undirected and same definition as above. - *Strongly connected component:* A directed walk from any node $v_i$ to $v_j$ (and the other way around) exists for all $v_i, v_J \in V^\prime$. ## Degrees - The degree of node $v_i$ is the number of edges $k_i$ it has. - The average degree of a network is the average over all nodes of the graph $\vert V \vert := n$. $ \frac{1}{n} \sum_ik_i = \frac{\sum_{i,j} A_{ij}}{n} = \frac{2m}{n} $ >[!note:] >The sum of all degrees is equal to the sum of the undirected adjacency 0/1 matrix (without self-loops). This is also equal to 2 times the number of edges $m$ (2 times because an edge affects 2 nodes in the degree calculation). **Degree distribution:** We construct a histogram showing the number (fraction) of nodes having a certain degree. In most real-world problems, these exhibit a power-law distribution. ![[network-degree-distribution.jpeg|center|450]] $ \begin{aligned} \log p_k&=-\alpha \log k+c \\[4pt] p_k &= k^{-\alpha}*c \end{aligned} $ >[!note:] In a power-law distribution, when we take the log on both axes (number of nodes, degree of node), the relationship turns linear. ## Edge Density Number of edges $m$ divided by the number of possible edges. When self-loops are allowed, then the denominator increases to $n^2$. $ \rho=\frac{m}{n \choose 2} =\frac{\sum_{i,j} A_{ij}}{n*(n-1)} $ - *Sparse network:* As the number of nodes grows larger, the number of edges does not grow proportionally with the number of nodes. Thus edge density converges to $0$ as $n \to \infty$. E.g. in a friendship network each node (person) has a constant number of friends $c$, irrespective of the size of the network. $ \rho = \frac{cn}{n \choose 2} \xrightarrow{n \to \infty} 0 $ - *Dense network:* The number of nodes grows proportionally with the number of nodes. Thus the edge density $\rho$ converges to a constant gt;0$. ## Other Properties **Diameter:** The diameter of a graph is the largest distance $d_{ij}$ between any two nodes $v_i,v_j \in V$. In an unweighted graph, distance is the length (number of edges) on the shortest path (geodesic path). $ \text{diameter}= \max_{i,j \in V} d_{ij} $ **Average path length:** Average distance between all node combinations of the network. In an undirected graph, we only sum distances where $i \le j$ to avoid double-counting of distances. $ \text{avg. path length}=\frac{1}{n \choose 2}\sum_{i \le j}d_{ij} $ >[!note:] >Since the distance of unconnected nodes cannot be calculated, these measures are computed per connected component. >[!note:] >The algorithms for finding the shortest-path are “breath-first-search” for unweighted graphs and “Dijkstra’s algorithm for weighted graphs.