How can I get communities without loop?

[yhhu99]

Thanks for making this great package available! It is useful to coarse a complicated graph.

But if I want to get a coarsen graph (whose each vertex represents a community) that is a DAG from a complicated graph, what should I do to achieve it?

Take Modularity partition for example. I added a function in 'GraphHelper.h' to judge whether a graph is a DAG or not. Firstly, I want to add some codes in function 'ModularityVertexPartition::diff_move()' to modify the improvement of a node-moving according to whether the graph is a DAG after moving.

But I found it difficult to get the coarsen graph after moving. So could you please tell me how can I get the graph after node-moving, or is there any other methods to ensure the result of leidenalgo is a DAG?

Thanks a lot!

[yhhu99]

I tried to realize as follows:

in 'GraphHelper.h' line113, added: inline bool is_dag() {igraph_bool_t res; graph_is_dag(this->_graph, res); return res;} to judge whether a graph is a DAG.

in 'ModularityVertexPartition::diff_move()' , I added as follows:

But after compile and install, it will return 'Segmentation fault (core dump)' when I call python API: la.find_partition(G, la.ModularityVertexPartition)

I don't know where I was mistaken.

[vtraag]

Hi @yhhu99, it is not entirely clear what your aim is. If you simply want to get a DAG out of any given graph, there are probably more useful methods.

If you simply look at the strongly connected components, then the contraction of those components will give you a DAG (this is called a condensation, see https://en.wikipedia.org/wiki/Strongly_connected_component for more details).

Alternatively, you could try to remove edges that violate the DAG property. The set of edges that need to be removed is known as a feedback arc set, see https://en.wikipedia.org/wiki/Feedback_arc_set.

But, if for some reason you want to cluster the graph while trying to satisfy some DAG criterion, you could try to explore this further. There are two points to be made about the code you post above.

(1) Getting the correct result from igraph you need to call it like this:

igraph_bool_t res;
igraph_is_dag(this->_graph, &res);
return res;

The way you are doing it now, you never allocate memory for the pointer *res, meaning that it points to just a random location in memory, which triggers the segmentation fault. You don't need to allocate memory for it when not defining it as a pointer, you can just pass in the address of the local variable res by passing &res.

(2) You are now simply checking recurrently whether the current graph is a DAG, not whether the aggregated graph based on the membership would be a DAG. This would be then as follows:

bool is_dag = this->get_graph()->collapse_graph(this)->is_dag();

The function collapse_graph will create the aggregate graph based on the current partition (which is this). Since you want to know the aggregation based on the difference in the membership, you can probably better make a function collapse_graph(vector<size_t> membership) so that you can pass in an arbitrary membership list (which you can then of course all call from within collapse_graph(MutableVertexPartition* partition). That way, you call it once with this->_membership and once with membership_copy.

Finally, it would be more convenient if you can copy-paste the actual code instead of screenshots, that would make it easier to provide some feedback.

Good luck! Let me know if you need some more help.

[yhhu99]

Hi @yhhu99, it is not entirely clear what your aim is. If you simply want to get a DAG out of any given graph, there are probably more useful methods.

If you simply look at the strongly connected components, then the contraction of those components will give you a DAG (this is called a condensation, see https://en.wikipedia.org/wiki/Strongly_connected_component for more details).

Alternatively, you could try to remove edges that violate the DAG property. The set of edges that need to be removed is known as a feedback arc set, see https://en.wikipedia.org/wiki/Feedback_arc_set.

But, if for some reason you want to cluster the graph while trying to satisfy some DAG criterion, you could try to explore this further. There are two points to be made about the code you post above.

(1) Getting the correct result from igraph you need to call it like this:

igraph_bool_t res;
igraph_is_dag(this->_graph, &res);
return res;

The way you are doing it now, you never allocate memory for the pointer *res, meaning that it points to just a random location in memory, which triggers the segmentation fault. You don't need to allocate memory for it when not defining it as a pointer, you can just pass in the address of the local variable res by passing &res.

(2) You are now simply checking recurrently whether the current graph is a DAG, not whether the aggregated graph based on the membership would be a DAG. This would be then as follows:

bool is_dag = this->get_graph()->collapse_graph(this)->is_dag();

The function collapse_graph will create the aggregate graph based on the current partition (which is this). Since you want to know the aggregation based on the difference in the membership, you can probably better make a function collapse_graph(vector<size_t> membership) so that you can pass in an arbitrary membership list (which you can then of course all call from within collapse_graph(MutableVertexPartition* partition). That way, you call it once with this->_membership and once with membership_copy.

Finally, it would be more convenient if you can copy-paste the actual code instead of screenshots, that would make it easier to provide some feedback.

Good luck! Let me know if you need some more help.

Thanks a lot for your help! I think I know how to get my work done.

Thanks again!

[vtraag]

Ok, great, I'll then close this issue. If something else comes up, feel free to reopen it (if it is about the same topic), or open a new issue.