Skip to content

Latest commit

 

History

History
28 lines (17 loc) · 2.33 KB

8.md

File metadata and controls

28 lines (17 loc) · 2.33 KB

8. Network Science: Graph Theory

Graph theory is a branch of mathematics for the study of discrete structures called graphs for modelling pairwise relations between objects.

I will skip graph's terminology, notation and basics, but it is present on professor's slides

Clustering coefficient

Clustering is a measure of how "bunched up" the edges of a graph are. Formally, the clustering coefficient of a node A is defined as the probability that two randomly selected friends of A are friends themselves. The clustering coefficient of a node is defined only if A hss at least two friends and it is always a value between 0 and 1.

The clustering coefficient (CC) of a graph G is the average of the clustering coefficients of all nodes in G. It quantifies the likelihood that nodes that share a common neighbor are neighbors themselves. It can be intended also as the proportion of all possible triangles that are actually closed in a graph.

Edge density

Edge density ρ of a graph is the actual number of edges in proportion to the maximum possible number of edges. Clearly it is a number between 0 and 1 and quantifies the probability that two nodes are connected.

If ρ is small, then the graph is sparse, otherwise it is dense

We consider a graph to be highly clustered if CC >> ρ

Centrality metrics

For nodes in a graph, centrality metrics try to formalize notions such as "important", "influential" or "popular". Since different notions of centrality exist, we have different centrality metrics.

  • The degree centrality simple say that the greater the degree of a node, the more "important" is the node. Unfortunately, it is not able to capture the notion of brokerage i.e. the ability of a node in a graph to act as a bridge between different components.
  • The betweenness of a node u is defined as the fraction of all pairwise shortest paths that go through u.
  • The closeness is a good metrics when is not important to have many friends or to be in a broker position, but it is important to be in a central position. It is defined as the inverse average shortest path length between a node u and every other node in the graph.
  • The eigenvector centrality is based on the idea that the importance of a node is determined by the importance of its neighbors.