Analytical Approaches

Degree is most commonly used, but there are other measures of the relative importance of a single node in a network.

Analytical Approaches

Analytical Approaches

• Concepts
  • Graph/Network correspondence
  • Node/Vertex correspondence
  • Edge directedness
    • Usually a network property
  • Multigraph
    • Allow multiple edges between nodes
  • Hypergraph
    • Allow edges to connect more than 2 nodes

Analytical Approaches

• Network measures
  • Shortest path length
    • Shortest traversal distance between two nodes
    • Can be weighted if edges have weights or hops if not
  • Node degree
    • Indegree: # of edges for which this node is a target
    • Outdegree: # of edges for which this node is a source
    • Degree (undirected): # of edges incident to this node
  • Hub
    • node with an exceptionally high degree
  
  
  
  
  
  
  
  
  
  
  
  

Analytical Approaches

• Network measures
  • Diameter: the largest distance between two nodes
  • Radius: the minimum of the maximum path between any two nodes
  • Characteristic path length: average shortest path length
  • Density: extent to which a network is fully connected
  • Heterogeneity: tendency of the network to contain hub nodes
  • Connected components: number of disconnected groups of nodes

Analytical Approaches

• Network measures
  • Clustering coefficient
    • Measures how close the neighbors of a node are to being a clique (fully connected)
    • $C_{\mathrm{node}}=\frac{2\mathrm{(\#\; of\; edges\; connecting\; a\; node\text{'}s\; neighbors)}}{\mathrm{(the\; node\text{'}s\; degree)}\mathrm{(the\; node\text{'}s\; degree\; -\; 1)}}$

Analytical Approaches

• Centrality - measures of node importance
  • Degree centrality (find hubs)
    • $C_{\mathrm{D}}\mathrm{(node)}=\frac{Degree\; of\; this\; node}{(\#\; of\; nodes\; –\; 1)}$
  • Betweenness centrality (bottleneck)
    • $C_{\mathrm{B}}\mathrm{(node)}=\frac{The\; average\; number\; of\; shortest\; paths\; that\; go\; through\; this\; node}{(\#\; of\; pairs)}$
  • Closeness centrality
    • $C\mathrm{(node)}=\frac{Sum\; of\; all\; shortest\; paths\; between\; this\; node\; and\; all\; other\; nodes}{(\#\; of\; nodes\; -\; 1)}$

Analytical Approaches

• Scale-free networks
  • Degree distribution follows a power law:
    P(k) ~ k^-y, where y is a constant
  • Distinct "hubs" (essential proteins?)
  • Resilient to perturbation
  • Biological (and social) networks tend to be scale-free

Analytical Approaches

Analytical Approaches

• Other techniques
  • Guilt-by association
    • Combine weak signals to get a stronger one
  • Over-representation analysis
    • Also called enrichment analysis
    • Statistical technique to determine if a set of terms are over-represented (enriched) in a network (or subnetwork)
  • Clustering
    • Also called unsupervised classification
    • Variety of techniques for group nodes based on attributes or connectivity

Analytical Approaches

• Other techniques
  • Motif finding
  • Finding subnetworks of interest

Cytoscape Apps for Graph Analysis