How to generate acyclic random graphs in igraph?












0















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







share|improve this question























  • 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
















0















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







share|improve this question























  • 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














0












0








0








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







share|improve this question














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






share|improve this question













share|improve this question











share|improve this question




share|improve this question










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



















  • 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












1 Answer
1






active

oldest

votes


















3















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]


enter image description here



grid = IGSquareLattice[{10, 10}];

HighlightGraph[grid, IGRandomSpanningTree[grid], GraphHighlightStyle -> "DehighlightHide"]


enter image description here




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:



enter image description here



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.






share|improve this answer
























  • 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











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
});


}
});














draft saved

draft discarded


















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









3















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]


enter image description here



grid = IGSquareLattice[{10, 10}];

HighlightGraph[grid, IGRandomSpanningTree[grid], GraphHighlightStyle -> "DehighlightHide"]


enter image description here




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:



enter image description here



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.






share|improve this answer
























  • 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
















3















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]


enter image description here



grid = IGSquareLattice[{10, 10}];

HighlightGraph[grid, IGRandomSpanningTree[grid], GraphHighlightStyle -> "DehighlightHide"]


enter image description here




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:



enter image description here



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.






share|improve this answer
























  • 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














3












3








3








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]


enter image description here



grid = IGSquareLattice[{10, 10}];

HighlightGraph[grid, IGRandomSpanningTree[grid], GraphHighlightStyle -> "DehighlightHide"]


enter image description here




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:



enter image description here



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.






share|improve this answer














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]


enter image description here



grid = IGSquareLattice[{10, 10}];

HighlightGraph[grid, IGRandomSpanningTree[grid], GraphHighlightStyle -> "DehighlightHide"]


enter image description here




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:



enter image description here



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.







share|improve this answer












share|improve this answer



share|improve this answer










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



















  • 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




















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







-

Popular posts from this blog

Guess what letter conforming each word

Image
6 $begingroup$ This is an entry in the Fortnightly Topic Challenge #41: Short and Sweet. 1 letter only could be mean anything . With an additional letter in front , could be used as medicine component and something you definitely learn or at least heard once. Add another letter in front , you would possibly hear that many times . Add an additional letter in front , you would found an independent country . With an additional letter, in the end , you would found something related to apple . Add another letter in the end , you would found something bad . Hint: Each letter is unique . word knowledge letters chemistry share | improve this question ...
Read more

Port of Spain

Image
For ports in the country of Spain, see List of ports in Spain. City in City of Port of Spain, Trinidad and Tobago Port of Spain City City of Port of Spain Top to bottom (left to right): Skyline of Port of Spain from Gulf of Paria; National Academy for the Performing Arts, Independence Square, Eric Williams Plaza; MovieTowne, Port of Port of Spain Motto(s):  "We Gather Strength As We Go Along" Port of Spain Coordinates: 10°40′N 61°31′W  /  10.667°N 61.517°W  / 10.667; -61.517 Coordinates: 10°40′N 61°31′W  /  10.667°N 61.517°W  / 10.667; -61.517 Country   Trinidad and Tobago Jurisdiction City of Port of Spain Settled 1560 Incorporated (town) 1853 Incorporated (city) 1914 Government  • Mayor Joel Martinez  • Governing body City Corporation Area [1]  • City 12 km 2 (5 sq mi) Elevation [2] 66 m (217 ft) Population (2011) [1]  • City 37,074  • Rank 3rd  • Density 3,090/km 2 (8,000/sq mi)...
Read more

Run scheduled task as local user group (not BUILTIN)

Image
0 I am trying to run a scheduled task with User Group (not a single user). This is working fine when I in the field "when running a task, use the following user account:" insert BUILTIN User Group (for example: Administrators or Users). But when I try it with the created Local User Group (example: TestGroup) it is not working. The Users in the TestGroup are the same as in the Administrators group. What could be the problem? Are there some restrictions to the Created User Group compared to BUILTINUsers? scheduled-tasks taskscheduler windowstaskschedule share | improve this question asked Nov 15 '18 at 15:36 Far...
Read more