Transcript Informatics tools in network science - LINK

Informatics tools in network
science
seminar 3
Measurements
Network Topology
Simple examples
What else?
• Network Skeleton
• Visualization (largescale?)
• Fractal properties
• Etc.
Degree centrality
6
1
3
4
5
7
2
Node
Score
Standardized
Score
1
1
1/6
2
1
1/6
3
3
3/6 = 1/2
4
2
2/6 = 1/3
5
3
3/6 = 1/2
6
2
2/6 = 1/3
7
2
2/6 = 1/3
Network degree centrality
n*: node with highest degree
The higher the value of the measure the higher
the difference of the node with the highest
Degree Centrality to all other nodes in the
network is.
Infinite:
Minimal:
Betweenness Centrality
The Betweenness Centrality is the normalized number of
shortest paths going through a node in a network.
Closeness centrality
The Closeness Centrality is the normalized number of steps required
to access every other node from a given node in a network.
Length of the shortest path
Eigenvector centrality, PageRank
Eigenvector centrality
PageRank
Clustering coefficient
Global clustering coefficient
The local clustering coefficient of a vertex in a graph quantifies
how close its neighbors are to being a clique (complete graph).
C = 1/3
Clustering coefficient
Scale-free network
Random graph
degree distribution
(the clustering coefficient behaves the same)
Network motifs
Topological Overlap
the ratio of shared nodes over the
number of nodes reachable from a
particular pair of nodes
Minimal (0)
Maximal (1)
Diameter and Density
The Diameter considers the largest geodesic distance
between any pair of nodes in a network.
The measure Density is the proportion of possible
edges that are actually present in the network.
Module measurements
Effective number of modules
Overlap value of elements (e.g. effective number of module belongs)
Bridgeness value of elements:
The bridgeness measure of an element or link as the
overlap of the given element or link between two or
more modules relative to the overlap of the other
elements or links.
T is the area-overlap, or common area of element between modules
.
The total bridgeness of element i describes the
bridgeness of that element between all modules:
Module similarity of elements:
The similarity of the elements i and j is based on their module membership vectors, di and dj :
Network capacity
e.g. Maximal flow (minimal cut) problem
Robustness
Structural cohesion: how many node needs to
be removed to disconnect the graph
2
1
5
Network connectivity
Average geodesic length (the characteristic
Path length): normalized average length of all
shortest path in the network
infinite in case of disconnected graph
Inverse geodesic length
Effective number
eî
30
30
100
pi 
pi log( pi )
30
25
20
20
60
2
1
1
vi

j
vj
average
sum
eff. num
25
27.5
165
5.975
1
27.5
165
1.570
Take home messages
• separate the giant component (if exists)
• compare measurements (test graph families, controll networks)
• use effective numbers
• check distributions
Programs
•R
• ModuLand
• Pajek
• Cytoscape with plugins:
– NetworkAnalyzer: distributions
– NetMatch: Motif search
– GraMoFoNe: Graph Motif For Networks
– CentisCaPe: centrality values
• (lényegiDB)
• + python modules
Python