SMA

• A distribution metric
• Defined as the number of edges incident to a node (degree of a node).
• Can be interpreted in terms of the "immediate risk" of a node to catch whatever is flowing through the network
• In directed graphs --> in-degree is often interpreted as a form of popularity, and the out-degree as a propensity to follow the behavior of others (heard/gregarious behavior)
• Heard behaviour --> Individuals observe the actions of all (or most) other individuals and act in a form aligned with them (example online auctions or restaurant reviews)

Normalize the quantity with respect to the total number of vertices in the graph (n-1 because we don't want to consider the node we are investigating. We want to consider the node on top and all the rest below)

• Based on the idea that an individual who is closer to other individuals in a social network is central because s/he can quickly interact with other actors
• The simplest way to calculate this centrality is therefore to consider the sum of the distances to all the other nodes of the graph.
• The higher the degree centrality of a vertex, the higher is that nodes' centrality

First calculate 1 divided by the sum of distances (edges) between a node and all other nodes

Then normalize: closeness centrality x (number of nodes -1)

It counts the number of shortest paths a vertex is part of. The higher the number, the more central a node is. 

2 x actual edges = 2 x 4 = 8

potential edges = 4 x (4-1) = 12

8 / 12 = 0.66

A Segmentation metric

It is defined as the minimum number of actors or ties of a social network that must be removed to disconnect the group.

It is therefore identical to the concept of connectivity of the nodes of a given graph.

Neo4j

Ususally where the giant component appears. If you go below, then the network goes from a connected state to a fragmented state. 

Clustering: data is often not linked, works on the distance similarity matrix 

Community detection: data is linked, algorithms use data property

Agglomerative clustering: 1. Initialize each node as a community. 2.Choose two communities satisfying certain criteria and merge them into larger ones. 

Divisive clustering: We start from a unique community and we partition it into smaller communities. Network-centric methods can be applied for partitioning

Goal: build a hierarchical structure of communities based on network topology. 

1. Initialization:

   • Assign each node to its own community, making each node a separate community.

2. Modularity Optimization Iteration:

   • For each node, consider moving it to the neighboring community that results in the maximum increase in modularity.
   • Iterate through all nodes and perform the above step until no further improvement in modularity can be achieved.

3. Aggregation:

   • Create a new network where nodes represent the communities found in the previous step.
   • The weights of the edges between these new nodes are determined by the sum of the weights of the original edges between nodes in the corresponding communities.

4. Repeat:

   • Repeat steps 2 and 3 on the aggregated network until no further improvement in modularity is possible.

5. Result:

   • The final communities are the ones identified in the last iteration, and the algorithm stops

1. Calculate betweenness centrality • Compute the betweenness centrality for all edges in the network.

2. Edge removal

• Identify the edge with the highest betweenness centrality and remove it.
• This process disrupts the most central connections in the network.

3. Recalculate betweenness centrality

• Recalculate the betweenness centrality for all remaining edges.
• The removal of an edge affects the centrality of other edges, so this step is necessary to update the centrality values.

4. Repeat

• Repeat steps 2 and 3 until a certain criterion is met.
• This criterion could be the desired number of communities, a specific modularity threshold, or the absence of edges.

5. Community detection

• The resulting disconnected components (subgraphs) after edge removal are considered as communities.
• The number of communities is determined based on the stopping criterion.

Label propagation is a semi-supervised machine learning algorithm that assigns labels to previously unlabeled data points.

In graph theory, a random walk involves moving through a graph by randomly selecting neighboring nodes at each step. The choice of the next node is typically determined by the edges connecting the current node to its neighbors. This process can be repeated for a specified number of steps or until a certain condition is met.