R: All Nodes of Degree "N" that can be reached from Some Node

March 1, 2023

I was looking at this question here: Maximum number of nodes which can be reached from each node in a graph using igraph

Here, we are interested in finding out the maximum number of nodes that can be reached from any given node:

## Example graph
library(igraph)
set.seed(123)
g = erdos.renyi.game(15, 0.15, directed = TRUE)
plot(g)

# answer
sort(subcomponent(g, 2, mode="out"))
length(subcomponent(g, 2, mode="out"))

I had the following question: Is it possible to extend this code to find out the maximum number of nodes of degree "n" that can be reached from any given node?

For instance – suppose there is a graph of different people and their friendships:

set.seed(123)
library(igraph)

# Define a vector of names
names <- c("John", "Alex", "Jason", "Matt", "Tim", "Luke", "Shawn", "Henry", "Steven", "Scott", "Adam", "Jeff", "Connor", "Peter", "Andrew", "Dave", "Daniel", "Benjamin", "Joseph", "Martin")

# Create an empty graph with 20 nodes
g <- make_empty_graph(20)

# Add random edges between nodes to represent friendships
set.seed(123)  # for reproducibility
num_edges <- 40
edge_list <- sample(names, size = num_edges * 2, replace = TRUE)
edge_list <- matrix(edge_list, ncol = 2, byrow = TRUE)
g <- graph_from_edgelist(edge_list, directed = FALSE)

# Set the node names to be the names vector
V(g)$name <- names

# Plot the graph
plot(g, vertex.label.cex = 0.7, vertex.label.color = "black", vertex.label.dist = 2)

I want to find out :

The number of friends that John has
The number of friends each friend of John has
The number of friends that each friend of the friends of John has

In other words – what are the maximum number of nodes of degree 3 that can be reached from "John"?

Can someone please show me how to modify this code?

Thanks!

Note: In the subcomponent() function – since I am dealing with an "undirected graph", I think I will set the "mode" argument to "all" (https://igraph.org/r/doc/subcomponent.html)

>Solution :

If you want to find out how many nodes are are within three jumps, you can use the distances command. For example

distances(g, "John")
#     John Alex Jason Matt Tim Luke Shawn Henry Steven Scott Adam Jeff Connor
# John    0    1     2    1   2    3     3     2      3     1    2    2      2
#      Peter Andrew Dave Daniel Benjamin Joseph Martin
# John     3      1    3      3        2      4      1

That gives you the distance to all the nodes, then you can just count those that are <=3