3

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)

enter image description here

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)

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
stats_noob
  • 5,401
  • 4
  • 27
  • 83

2 Answers2

2

Try ego

> length(unlist(ego(g, 3, "John")))
[1] 19

or if you want data.frame like below

> stack(as.data.frame(distances(g, "John", unlist(ego(g, 3, "John")))))
   values      ind
1       0     John
2       1     Alex
3       1     Matt
4       1    Scott
5       1   Andrew
6       1   Martin
7       2      Tim
8       2    Henry
9       2   Connor
10      2    Jason
11      2     Adam
12      2     Jeff
13      2 Benjamin
14      3     Luke
15      3     Dave
16      3    Shawn
17      3   Steven
18      3    Peter
19      3   Daniel
ThomasIsCoding
  • 96,636
  • 9
  • 24
  • 81
  • @ ThomasIsCoding: thank you so much for your answer! Is it possible to convert this into a dataframe? e.g. col1 = name, col2 = distance value? thank you so much! – stats_noob Mar 01 '23 at 19:45
  • I assigned this to an "object" like this: a = stack(as.data.frame(distances(g, "John", unlist(ego(g, 3, "John"))))) – stats_noob Mar 01 '23 at 19:56
  • I am working on this question here - can you please take a look at it if you have time later? https://stackoverflow.com/questions/75608347/r-creating-a-random-subgraph-from-a-starting-node thank you so much for all your help that you provided in the past few days! I really appreciate it! – stats_noob Mar 01 '23 at 19:58
1

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

sum(distances(g, "John")<=3)
# [1] 19

Note this does count John himself so it would be 18 other people. Only "Joseph" is more than 3 away from "John."

MrFlick
  • 195,160
  • 17
  • 277
  • 295
  • Is it possible to convert "distances(g, "John")" into a data frame? e.g. df = data.frame(distances(g, "John"))? – stats_noob Mar 01 '23 at 19:40
  • It returns a named vector. You can can turn a named vector into a data.frame in one of many ways: https://stackoverflow.com/questions/16816032/convert-named-character-vector-to-data-frame – MrFlick Mar 01 '23 at 19:51