Random graphs, fully-connected graphs

Specific Domains Graphs
,
1

Hi,
How does one create a fully connected graph with LightGraphs.jl? I looked at the documentation and did not see an obvious function.

A second equation is how to create a random graph with p percent of the edges?
I did find a function that allowed me to create a graph with Nv vertices and Ne edges, so I could create the conversion. But I assume there is a built-in function that can duplicate the desired functionality.

A third question would be how to create a network such that connections between a point and neighbors do not extend beyond a specified distance. Again, one can create the appropriate routine, but an efficient implementation might already be a part of the library.

Thanks.

Gordon

2

@anon94023334 ^

3

@dilumaluthge: I cannot see the reply! Or are you referring to somebody who might know the answer? If so, thanks!

4

I’m just pinging Seth, who can probably answer these questions. I myself do not know the answers to these questions.

5

I looked at the source code of LightGraphs and did not find what I was looking for. But then I found SpecialGraphs.jl, which has the function CompleteGraph, which computes an all-to-all connection. Interesting that since one needs to implement the required Interface to LightGraphs to gets its functionality, that these SpecialGraphs try to find alternative shortcuts to implement this interface when the graph has special structure. A CompleteGraph has special structure. I will try it out.

Thanks for the motivation.

6

How does one create a fully connected graph with LightGraphs.jl? I looked at the documentation and did not see an obvious function.

Do you mean a complete graph? If you’re on 1.3.x, use complete_graph(n). If on master, use SimpleGraph(LightGraphs.Generators.Complete(n)).

A second equation is how to create a random graph with p percent of the edges?

Use erdos_renyi() if on 1.3.x, or SimpleGraphs(LightGraphs.Generators.ErdosRenyi()) on master. ne can be calculated via p*nv*(nv-1) ÷ 2 for an undirected graph, so you could also do SimpleGraph(nv, p * nv * (nv - 1) ÷ 2).

A third question would be how to create a network such that connections between a point and neighbors do not extend beyond a specified distance.

What do you mean by “distance”? SimpleGraphs are unweighted (that is, default weight is 1). If “distance” means “weight”, then you can probably do this using SimpleWeightedGraphs and just bound the weight matrix.

7

Thanks! I do not understand the 1.3x versus master comment. I am on Julia 1.4x. While waiting for your response, I came across SpecialGraphs and used cg = SpecialGraphs.CompleteGraph(nverts). I assume both approach generate the same results since they both implement the desired interface?

8

I don’t know anything about SpecialGraphs, so I can’t comment.

1.3.x is the current stable version of LightGraphs. If you did a Pkg.add then this is what you’re using. If you did a Pkg.dev, then you’re on master, which has some major API changes.

If complete_graph() works without any warnings, then you’re on 1.3.x.

9

Ok, great. I will stick with what I have, but look forward to trying Pkg.dev in the near future. Has the documentation been updated for the master? When is the expected release date (give or take a few months.) Thanks.

10

Documentation is in progress, but the docstrings are up to date. Release is expected later this summer.

11

I switched to master yesterday and had to replace a couple of occurrences of erdos_renyi() in my code. This comment now made me a bit uncertain. Shouldn’t erdos_renyi(N, p) become something like LightGraphs.SimpleGraph(LightGraphs.Generators.ErdosRenyi(N, round(Int, p * nv * (nv - 1) / 2))), or LightGraphs.SimpleGraph(LightGraphs.Generators.ErdosRenyi(N, round(Int, binomial(N, 2)*p)))? So basically divide by 2 what you are suggesting? I may well be wrong though – just checking.

12

No, you’re right. If you use the ErdosRenyi generator with a SimpleDiGraph then you’ll want to NOT divide by 2. But since a SimpleGraph has undirected edges, you’ll need to divide by two. I’ll fix my previous reply. Thanks.

13

Thanks for the clarification!

14

Can a node link to itself in LightGraphs?

15

In general, yes; but some algorithms don’t like self-loops too much. Specifically, shortest-path calculations might have an issue. It’s not really supported for anything beyond representing a structure.

16

Do you know anything about SIR models? That is why I need it. Of course, I am not working in the most optimized fashion, I know.

Here is another question. I defined a graph with 10 nodes and 7 edges. I would like to add additional edges with add_edges(graph, src, dst) . When printing the edges, I notice that existing edges are overwritten as opposed to new edges created. That was unexpected. Is this what you’d expect? Here is what I did:

nedges = 7
nverts = 10

dg = DiGraph(nverts, nedges)

for i in 1:nverts
    add_edge!(dg, i, i)    # self-links
end
17

When printing the edges, I notice that existing edges are overwritten as opposed to new edges created.

I don’t know what you mean. Self-loops are not created by default, so they will not “overwrite” anything when you create them, since there’s nothing to overwrite:

julia> g = DiGraph(10, 7)
{10, 7} directed simple Int64 graph

julia> collect(edges(g))
7-element Array{LightGraphs.SimpleGraphsCore.SimpleEdge{Int64},1}:
 Edge 4 => 1
 Edge 4 => 3
 Edge 6 => 2
 Edge 6 => 5
 Edge 7 => 1
 Edge 7 => 4
 Edge 9 => 8

julia> for i in vertices(g)
           add_edge!(g, i, i)
       end

julia> collect(edges(g))
17-element Array{LightGraphs.SimpleGraphsCore.SimpleEdge{Int64},1}:
 Edge 1 => 1
 Edge 2 => 2
 Edge 3 => 3
 Edge 4 => 1
 Edge 4 => 3
 Edge 4 => 4
 Edge 5 => 5
 Edge 6 => 2
 Edge 6 => 5
 Edge 6 => 6
 Edge 7 => 1
 Edge 7 => 4
 Edge 7 => 7
 Edge 8 => 8
 Edge 9 => 8
 Edge 9 => 9
 Edge 10 => 10
18

I was obviously mistaken. I rewrote a mwe this morning, and you are obviously correct. Thank you for your help.

using LightGraphs

nedges = 3
nverts = 5

# Create a directed graph
dg = DiGraph(nverts, nedges)

#List the edges
println("\n----> Graph edges, no self-connections")
for (i,e) in enumerate(edges(dg))
    println("Edge $i) #, src/dst: ", src(e), ",  ", dst(e))
end

for i in 1:nverts
    add_edge!(dg, i, i)
end

println("\n----> Added self-edges")
for (i,e) in enumerate(edges(dg))
    println("Edge $i) #, src/dst: ", src(e), ",  ", dst(e))
end

with output:

----> Graph edges, no self-connections
Edge 1) #, src/dst: 2,  1
Edge 2) #, src/dst: 3,  1
Edge 3) #, src/dst: 5,  4

----> Added self-edges
Edge 1) #, src/dst: 1,  1
Edge 2) #, src/dst: 2,  1
Edge 3) #, src/dst: 2,  2
Edge 4) #, src/dst: 3,  1
Edge 5) #, src/dst: 3,  3
Edge 6) #, src/dst: 4,  4
Edge 7) #, src/dst: 5,  4
Edge 8) #, src/dst: 5,  5