Week 5
Ch3 Hubs
hub → a center around which other things revolve or from which they radiate; a focus of
activity, authority, commerce, transportation, etc.
- high-degree nodes→ hubs
heterogeneity→ heterogeneous networks present a wide variability in the properties and
roles of their elements — nodes and/or links.
The importance of a node or link is estimated by computing its centrality.
The average degree of a network indicates how connected the nodes are on average.
- the average degree may not be representative of the actual distribution of degree
values→ when the nodes have heterogeneous degrees
closeness centrality→ way to measure the centrality of a node by determining how “close” it
is to the other nodes.
- if the distances are short on average, their sum is a small number → high centrality
- the inverse of the sum of distances of a node from all others
networkx
nx.closeness_centrality(G, node)
betweenness → a node is the more central, the more often it is involved in these processes
the betweenness centrality of a link → the fraction of shortest paths among all possible node
couples that pass through that link
- links with very high betweenness centrality often join cohesive regions of the
network→ communities
- betweenness can be used to locate and remove those links
the betweenness centrality depends on the size of the network
- we have to normalize the betweenness values in order to compare the centrality of
nodes or links in different networks
(𝑁−1)(𝑁−2)
- 2
networkx
nx.betweenness_centrality(G)
nx.edge_betweenness_centrality(G)
The statistical distribution of a centrality measure tells us how many elements — nodes or
links — have a certain value of centrality, for all possible values
, Chapter 5
Positive links represent friendship while negative links represent antagonism, and an
important problem in the study of social networks is to understand the tension between these
two forces.
Structural balance
Let’s say you have a clique or a complete network and you label each link with either a + or
a -. We’re assuming each pair of people are either friends or enemies. (A group of people
small enough to have this level of mutual awareness.)
We will refer to triangles with one or three +’s as balanced, since they are free of these
sources of instability, and we will refer to triangles with zero or two +’s as unbalanced.
We say that a labeled complete graph is balanced if every one of its triangles is balanced,
that is, if it obeys the following: for every set of three nodes, if we consider the three edges
connecting them, either all three of these edges are labeled + or else exactly one of them is
labeled +.
If a complete graph can be divided into two sets of mutual friends, with complete mutual
antagonism between the two sets, then it is balanced.
So, either everyone likes each other, or the world consists of two groups of mutual friends
with complete antagonism between the groups.
Structural balance theory can also be applicable to international relations.
Weakly balanced networks: there is no set of three nodes such that the edges among
them consist of exactly two positive positive edges and one negative edge. In any triangle
that contains at least two positive edges, all three nodes must belong to the same group.
The network contains no triangles with exactly two + edges.
Characterization of weakly balanced networks: if a labeled complete graph is weakly
balanced, then its nodes can be divided into groups in such a way that every two nodes
belonging to the same group are friends, and every two nodes belonging to different groups
are enemies.
Structural balance in non-complete networks
A non-complete graph is balanced if it can be completed by adding edges to form a signed
complete graph that is balanced.
We could define a signed graph to be balanced if it is possible to divide the nodes into two
sets X and Y, such that any edge with both ends inside X or both ends inside Y is positive,
and any edge with one end in X and the other in Y is negative.
If the graph contains a cycle with an odd number of negative edges, then this implies that the
graph is not balanced.
Ch3 Hubs
hub → a center around which other things revolve or from which they radiate; a focus of
activity, authority, commerce, transportation, etc.
- high-degree nodes→ hubs
heterogeneity→ heterogeneous networks present a wide variability in the properties and
roles of their elements — nodes and/or links.
The importance of a node or link is estimated by computing its centrality.
The average degree of a network indicates how connected the nodes are on average.
- the average degree may not be representative of the actual distribution of degree
values→ when the nodes have heterogeneous degrees
closeness centrality→ way to measure the centrality of a node by determining how “close” it
is to the other nodes.
- if the distances are short on average, their sum is a small number → high centrality
- the inverse of the sum of distances of a node from all others
networkx
nx.closeness_centrality(G, node)
betweenness → a node is the more central, the more often it is involved in these processes
the betweenness centrality of a link → the fraction of shortest paths among all possible node
couples that pass through that link
- links with very high betweenness centrality often join cohesive regions of the
network→ communities
- betweenness can be used to locate and remove those links
the betweenness centrality depends on the size of the network
- we have to normalize the betweenness values in order to compare the centrality of
nodes or links in different networks
(𝑁−1)(𝑁−2)
- 2
networkx
nx.betweenness_centrality(G)
nx.edge_betweenness_centrality(G)
The statistical distribution of a centrality measure tells us how many elements — nodes or
links — have a certain value of centrality, for all possible values
, Chapter 5
Positive links represent friendship while negative links represent antagonism, and an
important problem in the study of social networks is to understand the tension between these
two forces.
Structural balance
Let’s say you have a clique or a complete network and you label each link with either a + or
a -. We’re assuming each pair of people are either friends or enemies. (A group of people
small enough to have this level of mutual awareness.)
We will refer to triangles with one or three +’s as balanced, since they are free of these
sources of instability, and we will refer to triangles with zero or two +’s as unbalanced.
We say that a labeled complete graph is balanced if every one of its triangles is balanced,
that is, if it obeys the following: for every set of three nodes, if we consider the three edges
connecting them, either all three of these edges are labeled + or else exactly one of them is
labeled +.
If a complete graph can be divided into two sets of mutual friends, with complete mutual
antagonism between the two sets, then it is balanced.
So, either everyone likes each other, or the world consists of two groups of mutual friends
with complete antagonism between the groups.
Structural balance theory can also be applicable to international relations.
Weakly balanced networks: there is no set of three nodes such that the edges among
them consist of exactly two positive positive edges and one negative edge. In any triangle
that contains at least two positive edges, all three nodes must belong to the same group.
The network contains no triangles with exactly two + edges.
Characterization of weakly balanced networks: if a labeled complete graph is weakly
balanced, then its nodes can be divided into groups in such a way that every two nodes
belonging to the same group are friends, and every two nodes belonging to different groups
are enemies.
Structural balance in non-complete networks
A non-complete graph is balanced if it can be completed by adding edges to form a signed
complete graph that is balanced.
We could define a signed graph to be balanced if it is possible to divide the nodes into two
sets X and Y, such that any edge with both ends inside X or both ends inside Y is positive,
and any edge with one end in X and the other in Y is negative.
If the graph contains a cycle with an odd number of negative edges, then this implies that the
graph is not balanced.
