14.4 Network analysis and graph theory

Network analysis and graph theory are powerful tools for understanding complex systems. They allow us to model relationships between entities as nodes and edges, revealing hidden patterns and structures in data.

In R, packages like igraph and ggraph make it easy to create, analyze, and visualize networks. We'll learn how to represent graph data, calculate network metrics, detect communities, and create stunning visualizations to bring our networks to life.

Network Analysis Fundamentals

Key Concepts and Terminology

Top images from around the web for Key Concepts and Terminology

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

• 

  File:CPT-Graphs-undirected-unweighted-ex1.svg - Wikipedia View original

  Is this image relevant?

• 

  Graphs – An Open Guide to Data Structures and Algorithms View original

  Is this image relevant?

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

• 

  File:CPT-Graphs-undirected-unweighted-ex1.svg - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Key Concepts and Terminology

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

• 

  File:CPT-Graphs-undirected-unweighted-ex1.svg - Wikipedia View original

  Is this image relevant?

• 

  Graphs – An Open Guide to Data Structures and Algorithms View original

  Is this image relevant?

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

• 

  File:CPT-Graphs-undirected-unweighted-ex1.svg - Wikipedia View original

  Is this image relevant?

1 of 3

• Network analysis studies complex systems represented as graphs consisting of nodes (vertices) connected by edges (links or ties)
• Graphs can be directed (edges have a specific direction) or undirected (edges have no direction)
• Graphs can be weighted (edges have associated numerical values) or unweighted
• The degree of a node is the number of edges connected to it
  • In directed graphs, nodes have both in-degree (incoming edges) and out-degree (outgoing edges)
• A path is a sequence of nodes connected by edges
  • The shortest path between two nodes is called the geodesic distance
• Connectivity refers to the minimum number of nodes or edges that need to be removed to disconnect a graph
• Cliques are subsets of nodes in a graph that are all connected to each other, forming a complete subgraph (e.g., a triangle or a complete square)
• Bipartite graphs have two distinct sets of nodes, with edges only connecting nodes from different sets (e.g., a graph of students and courses they are enrolled in)

Graph Types and Properties

• Directed graphs have edges with a specific direction, indicating a one-way relationship between nodes (e.g., a citation network)
• Undirected graphs have edges with no direction, indicating a symmetric relationship between nodes (e.g., a friendship network)
• Weighted graphs have edges with associated numerical values, representing the strength or importance of the connection (e.g., a road network with distances as edge weights)
• Unweighted graphs have edges without any associated values, indicating only the presence or absence of a connection
• The degree distribution of a graph describes the frequency of nodes with different degrees and can provide insights into the structure and dynamics of the network (e.g., a scale-free network with a power-law degree distribution)

Network Data Representation in R

Creating Graph Objects

• The igraph package in R provides a comprehensive set of tools for network analysis and graph manipulation
• Network data can be represented using an adjacency matrix, where each cell (i, j) represents the presence or weight of an edge between nodes i and j
• Alternatively, network data can be represented using an edge list, which is a two-column matrix or data frame containing the source and target nodes for each edge
• The

  graph_from_adjacency_matrix()

  function in igraph creates graph objects from adjacency matrices
  • Example:

    g <- graph_from_adjacency_matrix(matrix(c(0,1,1,0), nrow=2), mode="undirected")

• The

  graph_from_edgelist()

  function in igraph creates graph objects from edge lists
  • Example:

    g <- graph_from_edgelist(matrix(c(1,2,2,3), ncol=2), directed=FALSE)

Manipulating Graph Objects

• The

  V()

  function accesses and manipulates node attributes of a graph object
  • Example:

    V(g)$name <- c("Alice", "Bob", "Carol")

    assigns names to nodes
• The

  E()

  function accesses and manipulates edge attributes of a graph object
  • Example:

    E(g)$weight <- c(0.5, 1.2)

    assigns weights to edges
• The

  %--%

  operator creates edges between nodes in a graph object
  • Example:

    g <- g + edge("Alice", "David")

    adds a new edge to the graph
• The

  +

  operator adds nodes or edges to an existing graph
  • Example:

    g <- g + vertices(c("Eve", "Frank"))

    adds new nodes to the graph

Network Metrics and Interpretation

Centrality Measures

• Centrality measures quantify the importance or influence of nodes in a network based on their position and connectivity
• Degree centrality is the simplest measure, based on the number of edges connected to a node
  • Calculated using the

    degree()

    function in igraph
  • Example:

    degree(g)

    returns the degree of each node in the graph
• Betweenness centrality measures the extent to which a node lies on the shortest paths between other nodes, acting as a bridge
  • Calculated using the

    betweenness()

    function in igraph
  • Example:

    betweenness(g)

    returns the betweenness centrality of each node
• Closeness centrality measures the average shortest path distance from a node to all other nodes in the network
  • Calculated using the

    closeness()

    function in igraph
  • Example:

    closeness(g)

    returns the closeness centrality of each node
• Eigenvector centrality measures the influence of a node based on the importance of its neighbors
  • Calculated using the

    eigen_centrality()

    function in igraph
  • Example:

    eigen_centrality(g)$vector

    returns the eigenvector centrality of each node

Community Detection

• Community detection algorithms identify groups of nodes that are more densely connected to each other than to nodes in other groups
• The

  cluster_walktrap()

  function in igraph implements a community detection algorithm based on random walks
  • Example:

    cluster_walktrap(g)

    returns a community structure object
• The

  cluster_louvain()

  function in igraph implements a community detection algorithm based on modularity optimization
  • Example:

    cluster_louvain(g)

    returns a community structure object
• The

  membership()

  function extracts the community assignments from a community structure object
  • Example:

    membership(cluster_walktrap(g))

    returns a vector of community assignments for each node

Visualizing Networks in R

Basic Visualization with igraph

• The

  plot()

  function in igraph creates basic visualizations of graph objects, with customizable node and edge attributes
  • Example:

    plot(g, vertex.color="red", edge.arrow.size=0.5)

    plots the graph with red nodes and smaller edge arrows
• Node and edge attributes can be set directly in the

  plot()

  function or by modifying the graph object beforehand
  • Example:

    V(g)$color <- "blue"; plot(g)

    sets the node color to blue before plotting
• Layout algorithms determine the positioning of nodes in the visualization
  • Example:

    plot(g, layout=layout_in_circle(g))

    plots the graph with nodes arranged in a circular layout

Advanced Visualization with ggraph

• The ggraph package provides a grammar of graphics framework for creating more advanced and customizable network visualizations
• The

  ggraph()

  function creates a ggraph object from a graph object
  • Example:

    ggraph(g, layout="fr")

    creates a ggraph object with the Fruchterman-Reingold layout
• The

  geom_node_*()

  and

  geom_edge_*()

  functions specify the visual properties of nodes and edges
  • Example:

    ggraph(g) + geom_node_point(size=5) + geom_edge_link(color="gray")

    creates a visualization with large nodes and gray edges
• The layout parameter in

  ggraph()

  specifies the algorithm for arranging nodes
  • Example:

    ggraph(g, layout="kk")

    uses the Kamada-Kawai layout algorithm
• Node and edge aesthetics can be mapped to variables in the graph data using the

  aes()

  function
  • Example:

    ggraph(g) + geom_node_point(aes(size=degree(g)))

    maps node size to degree centrality
• Faceting and layering can be used to create small multiples or combine multiple network visualizations in a single plot
  • Example:

    ggraph(g) + geom_node_point() + facet_wrap(~community)

    creates a separate plot for each community in the graph