DANCEST 805 Lecture Notes - Lecture 13: Clustering Coefficient, Degree Distribution, Smallworld
1
Modelling Nature
Case study 3. An Experiment: It’s a Small World After All
Learning goals:
1. What is a network?
2. What are the different types of network models?
3. Elaborate on the scale-free network.
4. Elaborate on the social network.
Learning goal 1. What is a network?
A network is a system consisting of a number (=N) of similar nodes/actors (vertex/vertices),
where each node interacts with certain other nodes in the system.
- This interaction is visualized through a connection/link (edge or edges).
There are two different approaches to networks:
1. Egocentric network approach
a. Definition: provides a view of the network from the perspective of an actor in the network.
2. Whole network approach
a. Definition: provides a view of the whole structure of the environment.
Network topology vs. network properties.
- Network topology refers to the layout of a network, i.e. how different nodes in a network are
connected to each other and how they communicate is determined by the network’s topology.
o Based on the topology of a network the properties and characteristics of the network can be
analysed.
- Network properties define network models and can be used to analyse and compare different
network models and can be used to analyse and compare different network models.
o The properties are based on the network’s topology.
- Example: a property would be a small-world (SW) network.
o High clustering coefficient: many clusters of highly interconnected elements.
o Low characteristic path length: small number of connections between clusters.
A network has three characteristics:
1. Path length (L)
a. Definition: the distance between two nodes.
b. Shortest path length: path that connect the two nodes with the shortest amount of edges.
c. Average path length (L): the average number of
steps along the shortest paths for all possible pairs
of network nodes.
2. Clustering coefficient (C)
a. Definition: the fraction of associated neighbours of a node that are
also connected.
3. Degree (k) and degree distribution (P(k))
a. Degree (k)/branching factor: the number of
other nodes connected to this node;
i.e. the number of vertices of a node.
2
b. Degree distribution (P(k)): the number of nodes in the network that have a certain degree or
the proportion of nodes that have k links. Can be visualised in a bar diagram.
There are four other ways to classify networks:
1. Centralized, decentralized and distributed
2. Sparse vs dense networks
a. A sparse network exhibits a very small number of connections.
b. A dense network exhibits a lot of connections.
3. Directed vs undirected networks
a. With arrows in the connections.
4. Self-connection and multiple edges vs more complex networks
Learning goals 2. What are the different types of network models?
There are six types of network:
1. Random network
a. Definition: network that is generated by some random process.
b. Democratic -> most nodes have approx. the same amount of links and are
(randomly) connected, but not interconnected.
c. They are exponential, because the probability that a node is connected to k
other sites decreases exponentially for large k.
d. Plot distribution of node linkages: bell-shaped curve (each node has a the same
approx. the same number of links).
i. Therefore, it is extremely rare to find nodes that have significantly
more or fewer links than the average.
e. Example: highways across the US.
2. Fully connected network
a. Definition: network where each node is connected to all other nodes.
3. Regular network
a. Definition: network where each node has an identical connection scheme.
4. Scale-free network
a. Definition: network in which some nodes act as “highly connected hubs” (high degree, red),
although most nodes are of low degree (blue).
b. Hubs are popular nodes who have a tremendous amount of connections to other nodes, so a
very high number of links.
c. Some nodes have a few connections and some have a tremendous number of links. In that
sense, the system has no scale.
d. Plot distribution of node linkages: power law.
i. The power law does not have peaks, as a bell cuve does, but is instead decribed by a
continuously dececreasing function.
e. Example: airports across the US.
f. Thanks to the growing nature of real networks, older nodes had greater opportunities to
acquire links.
i. All nodes are not equal: preferential attachment.
Document Summary
An experiment: it"s a small world after all. Learning goals: what is a network, what are the different types of network models, elaborate on the scale-free network, elaborate on the social network. A network is a system consisting of a number (=n) of similar nodes/actors (vertex/vertices), where each node interacts with certain other nodes in the system. This interaction is visualized through a connection/link (edge or edges). Network properties define network models and can be used to analyse and compare different network models and can be used to analyse and compare different network models: the properties are based on the network"s topology. Example: a property would be a small-world (sw) network: high clustering coefficient: many clusters of highly interconnected elements. Low characteristic path length: small number of connections between clusters. 1: degree distribution (p(k)): the number of nodes in the network that have a certain degree or the proportion of nodes that have k links.
