How to generate acyclic random graphs in igraph?
I want to generate random acyclic graphs in the R igraph. I know that the function sample_pa generate for m=1 scale-free acyclic graphs according to the Barabasi-Albert model. I am interested if we can force igraph to generate acyclic graphs for higher values of m ? Or can we generate acyclic graphs according to some other algorithm in igraph R (or in some other R package) ? My aim is to generate acyclic graphs with different patterns of branching. Therefore, I am interested in these graphs.
r igraph
asked Nov 20 '18 at 16:46
Piotr WilczekPiotr Wilczek
60118
add a comment |
I want to generate random acyclic graphs in the R igraph. I know that the function sample_pa generate for m=1 scale-free acyclic graphs according to the Barabasi-Albert model. I am interested if we can force igraph to generate acyclic graphs for higher values of m ? Or can we generate acyclic graphs according to some other algorithm in igraph R (or in some other R package) ? My aim is to generate acyclic graphs with different patterns of branching. Therefore, I am interested in these graphs.
r igraph
asked Nov 20 '18 at 16:46
Piotr WilczekPiotr Wilczek
60118
Directed or undirected?
– Julius Vainora
Nov 20 '18 at 16:56
I am mainly interested in undirected graphs. But from directed graphs, it is always possible to obtain the undirected versions.
– Piotr Wilczek
Nov 20 '18 at 16:58
add a comment |
I want to generate random acyclic graphs in the R igraph. I know that the function sample_pa generate for m=1 scale-free acyclic graphs according to the Barabasi-Albert model. I am interested if we can force igraph to generate acyclic graphs for higher values of m ? Or can we generate acyclic graphs according to some other algorithm in igraph R (or in some other R package) ? My aim is to generate acyclic graphs with different patterns of branching. Therefore, I am interested in these graphs.
r igraph
asked Nov 20 '18 at 16:46
Piotr WilczekPiotr Wilczek
60118
I want to generate random acyclic graphs in the R igraph. I know that the function sample_pa generate for m=1 scale-free acyclic graphs according to the Barabasi-Albert model. I am interested if we can force igraph to generate acyclic graphs for higher values of m ? Or can we generate acyclic graphs according to some other algorithm in igraph R (or in some other R package) ? My aim is to generate acyclic graphs with different patterns of branching. Therefore, I am interested in these graphs.
r igraph
r igraph
asked Nov 20 '18 at 16:46
Piotr WilczekPiotr Wilczek
60118
asked Nov 20 '18 at 16:46
Piotr WilczekPiotr Wilczek
60118
asked Nov 20 '18 at 16:46
Piotr WilczekPiotr Wilczek
60118
asked Nov 20 '18 at 16:46
Piotr WilczekPiotr Wilczek
60118
asked Nov 20 '18 at 16:46
Piotr WilczekPiotr Wilczek
60118
60118
Directed or undirected?
– Julius Vainora
Nov 20 '18 at 16:56
I am mainly interested in undirected graphs. But from directed graphs, it is always possible to obtain the undirected versions.
– Piotr Wilczek
Nov 20 '18 at 16:58
add a comment |
Directed or undirected?
– Julius Vainora
Nov 20 '18 at 16:56
I am mainly interested in undirected graphs. But from directed graphs, it is always possible to obtain the undirected versions.
– Piotr Wilczek
Nov 20 '18 at 16:58
Directed or undirected?
– Julius Vainora
Nov 20 '18 at 16:56
Directed or undirected?
– Julius Vainora
Nov 20 '18 at 16:56
I am mainly interested in undirected graphs. But from directed graphs, it is always possible to obtain the undirected versions.
– Piotr Wilczek
Nov 20 '18 at 16:58
I am mainly interested in undirected graphs. But from directed graphs, it is always possible to obtain the undirected versions.
– Piotr Wilczek
Nov 20 '18 at 16:58
add a comment |
1 Answer
1
active
oldest
votes
I want to generate random acyclic graphs in the R igraph.
I am mainly interested in undirected graphs.
An acyclic undirected graph is a forest, i.e. a graph the connected components of which are trees.
I know that the function sample_pa generate for m=1 scale-free acyclic graphs according to the Barabasi-Albert model. I am interested if we can force igraph to generate acyclic graphs for higher values of m ?
This is mathematically impossible. A tree on n nodes has n-1 edges and a forest has fewer. For higher values of m in sample_pa there would be more edges, hence there would be cycles.
Or can we generate acyclic graphs according to some other algorithm in igraph R
Look through the random graph generators in igraph. Several of them will output trees. For example, check sample_growing with citation = TRUE.
However, none of these will sample trees uniformly. Presumably, instead of just generating any tree, you would want to know something about the distribution they are coming from.
Recently I contributed a uniform tree sampler, as well as a uniform spanning tree sampler to igraph, but it is not yet in the R interface. You can try it out with the Mathematica interface (or of course in C).
Table[IGTreeGame[10], 6]
grid = IGSquareLattice[{10, 10}];
HighlightGraph[grid, IGRandomSpanningTree[grid], GraphHighlightStyle -> "DehighlightHide"]
But from directed graphs, it is always possible to obtain the undirected versions.
But not acyclic ones.
It is easy to generate a random directed acyclic graph by randomly filling out the upper part of the adjacency matrix with the desired number of 1s.
When you convert this to undirected, it will not usually be acyclic.
For example, this is not acyclic as undirected:
In fact, any simple undirected graph can be oriented so that the directed version will be acyclic. There is little relationship between undirected acyclic and directed acyclic graphs.
answered Nov 21 '18 at 10:11
SzabolcsSzabolcs
16.1k361143
Thanks for your aswer. In the R igraph, besides the functions sample_growing ( ,m=1) and sample_pa( ,m=1), I did not find any other function which has as its output a tree.
– Piotr Wilczek
Nov 21 '18 at 19:46
@PiotrWilczek The one I mentioned is in the C core. I assume it will be in the next R interface.
– Szabolcs
Nov 21 '18 at 22:08
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53397697%2fhow-to-generate-acyclic-random-graphs-in-igraph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I want to generate random acyclic graphs in the R igraph.
I am mainly interested in undirected graphs.
An acyclic undirected graph is a forest, i.e. a graph the connected components of which are trees.
I know that the function sample_pa generate for m=1 scale-free acyclic graphs according to the Barabasi-Albert model. I am interested if we can force igraph to generate acyclic graphs for higher values of m ?
This is mathematically impossible. A tree on n nodes has n-1 edges and a forest has fewer. For higher values of m in sample_pa there would be more edges, hence there would be cycles.
Or can we generate acyclic graphs according to some other algorithm in igraph R
Look through the random graph generators in igraph. Several of them will output trees. For example, check sample_growing with citation = TRUE.
However, none of these will sample trees uniformly. Presumably, instead of just generating any tree, you would want to know something about the distribution they are coming from.
Recently I contributed a uniform tree sampler, as well as a uniform spanning tree sampler to igraph, but it is not yet in the R interface. You can try it out with the Mathematica interface (or of course in C).
Table[IGTreeGame[10], 6]
grid = IGSquareLattice[{10, 10}];
HighlightGraph[grid, IGRandomSpanningTree[grid], GraphHighlightStyle -> "DehighlightHide"]
But from directed graphs, it is always possible to obtain the undirected versions.
But not acyclic ones.
It is easy to generate a random directed acyclic graph by randomly filling out the upper part of the adjacency matrix with the desired number of 1s.
When you convert this to undirected, it will not usually be acyclic.
For example, this is not acyclic as undirected:
In fact, any simple undirected graph can be oriented so that the directed version will be acyclic. There is little relationship between undirected acyclic and directed acyclic graphs.
answered Nov 21 '18 at 10:11
SzabolcsSzabolcs
16.1k361143
Thanks for your aswer. In the R igraph, besides the functions sample_growing ( ,m=1) and sample_pa( ,m=1), I did not find any other function which has as its output a tree.
– Piotr Wilczek
Nov 21 '18 at 19:46
@PiotrWilczek The one I mentioned is in the C core. I assume it will be in the next R interface.
– Szabolcs
Nov 21 '18 at 22:08
add a comment |
I want to generate random acyclic graphs in the R igraph.
I am mainly interested in undirected graphs.
An acyclic undirected graph is a forest, i.e. a graph the connected components of which are trees.
I know that the function sample_pa generate for m=1 scale-free acyclic graphs according to the Barabasi-Albert model. I am interested if we can force igraph to generate acyclic graphs for higher values of m ?
This is mathematically impossible. A tree on n nodes has n-1 edges and a forest has fewer. For higher values of m in sample_pa there would be more edges, hence there would be cycles.
Or can we generate acyclic graphs according to some other algorithm in igraph R
Look through the random graph generators in igraph. Several of them will output trees. For example, check sample_growing with citation = TRUE.
However, none of these will sample trees uniformly. Presumably, instead of just generating any tree, you would want to know something about the distribution they are coming from.
Recently I contributed a uniform tree sampler, as well as a uniform spanning tree sampler to igraph, but it is not yet in the R interface. You can try it out with the Mathematica interface (or of course in C).
Table[IGTreeGame[10], 6]
grid = IGSquareLattice[{10, 10}];
HighlightGraph[grid, IGRandomSpanningTree[grid], GraphHighlightStyle -> "DehighlightHide"]
But from directed graphs, it is always possible to obtain the undirected versions.
But not acyclic ones.
It is easy to generate a random directed acyclic graph by randomly filling out the upper part of the adjacency matrix with the desired number of 1s.
When you convert this to undirected, it will not usually be acyclic.
For example, this is not acyclic as undirected:
In fact, any simple undirected graph can be oriented so that the directed version will be acyclic. There is little relationship between undirected acyclic and directed acyclic graphs.
answered Nov 21 '18 at 10:11
SzabolcsSzabolcs
16.1k361143
Thanks for your aswer. In the R igraph, besides the functions sample_growing ( ,m=1) and sample_pa( ,m=1), I did not find any other function which has as its output a tree.
– Piotr Wilczek
Nov 21 '18 at 19:46
@PiotrWilczek The one I mentioned is in the C core. I assume it will be in the next R interface.
– Szabolcs
Nov 21 '18 at 22:08
add a comment |
I want to generate random acyclic graphs in the R igraph.
I am mainly interested in undirected graphs.
An acyclic undirected graph is a forest, i.e. a graph the connected components of which are trees.
I know that the function sample_pa generate for m=1 scale-free acyclic graphs according to the Barabasi-Albert model. I am interested if we can force igraph to generate acyclic graphs for higher values of m ?
This is mathematically impossible. A tree on n nodes has n-1 edges and a forest has fewer. For higher values of m in sample_pa there would be more edges, hence there would be cycles.
Or can we generate acyclic graphs according to some other algorithm in igraph R
Look through the random graph generators in igraph. Several of them will output trees. For example, check sample_growing with citation = TRUE.
However, none of these will sample trees uniformly. Presumably, instead of just generating any tree, you would want to know something about the distribution they are coming from.
Recently I contributed a uniform tree sampler, as well as a uniform spanning tree sampler to igraph, but it is not yet in the R interface. You can try it out with the Mathematica interface (or of course in C).
Table[IGTreeGame[10], 6]
grid = IGSquareLattice[{10, 10}];
HighlightGraph[grid, IGRandomSpanningTree[grid], GraphHighlightStyle -> "DehighlightHide"]
But from directed graphs, it is always possible to obtain the undirected versions.
But not acyclic ones.
It is easy to generate a random directed acyclic graph by randomly filling out the upper part of the adjacency matrix with the desired number of 1s.
When you convert this to undirected, it will not usually be acyclic.
For example, this is not acyclic as undirected:
In fact, any simple undirected graph can be oriented so that the directed version will be acyclic. There is little relationship between undirected acyclic and directed acyclic graphs.
answered Nov 21 '18 at 10:11
SzabolcsSzabolcs
16.1k361143
I want to generate random acyclic graphs in the R igraph.
I am mainly interested in undirected graphs.
An acyclic undirected graph is a forest, i.e. a graph the connected components of which are trees.
I know that the function sample_pa generate for m=1 scale-free acyclic graphs according to the Barabasi-Albert model. I am interested if we can force igraph to generate acyclic graphs for higher values of m ?
This is mathematically impossible. A tree on n nodes has n-1 edges and a forest has fewer. For higher values of m in sample_pa there would be more edges, hence there would be cycles.
Or can we generate acyclic graphs according to some other algorithm in igraph R
Look through the random graph generators in igraph. Several of them will output trees. For example, check sample_growing with citation = TRUE.
However, none of these will sample trees uniformly. Presumably, instead of just generating any tree, you would want to know something about the distribution they are coming from.
Recently I contributed a uniform tree sampler, as well as a uniform spanning tree sampler to igraph, but it is not yet in the R interface. You can try it out with the Mathematica interface (or of course in C).
Table[IGTreeGame[10], 6]
grid = IGSquareLattice[{10, 10}];
HighlightGraph[grid, IGRandomSpanningTree[grid], GraphHighlightStyle -> "DehighlightHide"]
But from directed graphs, it is always possible to obtain the undirected versions.
But not acyclic ones.
It is easy to generate a random directed acyclic graph by randomly filling out the upper part of the adjacency matrix with the desired number of 1s.
When you convert this to undirected, it will not usually be acyclic.
For example, this is not acyclic as undirected:
In fact, any simple undirected graph can be oriented so that the directed version will be acyclic. There is little relationship between undirected acyclic and directed acyclic graphs.
answered Nov 21 '18 at 10:11
SzabolcsSzabolcs
16.1k361143
answered Nov 21 '18 at 10:11
SzabolcsSzabolcs
16.1k361143
answered Nov 21 '18 at 10:11
SzabolcsSzabolcs
16.1k361143
answered Nov 21 '18 at 10:11
SzabolcsSzabolcs
16.1k361143
16.1k361143
Thanks for your aswer. In the R igraph, besides the functions sample_growing ( ,m=1) and sample_pa( ,m=1), I did not find any other function which has as its output a tree.
– Piotr Wilczek
Nov 21 '18 at 19:46
@PiotrWilczek The one I mentioned is in the C core. I assume it will be in the next R interface.
– Szabolcs
Nov 21 '18 at 22:08
add a comment |
Thanks for your aswer. In the R igraph, besides the functions sample_growing ( ,m=1) and sample_pa( ,m=1), I did not find any other function which has as its output a tree.
– Piotr Wilczek
Nov 21 '18 at 19:46
@PiotrWilczek The one I mentioned is in the C core. I assume it will be in the next R interface.
– Szabolcs
Nov 21 '18 at 22:08
Thanks for your aswer. In the R igraph, besides the functions sample_growing ( ,m=1) and sample_pa( ,m=1), I did not find any other function which has as its output a tree.
– Piotr Wilczek
Nov 21 '18 at 19:46
Thanks for your aswer. In the R igraph, besides the functions sample_growing ( ,m=1) and sample_pa( ,m=1), I did not find any other function which has as its output a tree.
– Piotr Wilczek
Nov 21 '18 at 19:46
@PiotrWilczek The one I mentioned is in the C core. I assume it will be in the next R interface.
– Szabolcs
Nov 21 '18 at 22:08
@PiotrWilczek The one I mentioned is in the C core. I assume it will be in the next R interface.
– Szabolcs
Nov 21 '18 at 22:08
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53397697%2fhow-to-generate-acyclic-random-graphs-in-igraph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Directed or undirected?
– Julius Vainora
Nov 20 '18 at 16:56
I am mainly interested in undirected graphs. But from directed graphs, it is always possible to obtain the undirected versions.
– Piotr Wilczek
Nov 20 '18 at 16:58