Code Now

How does Label propagation algorithm works on directed graphs?

Recommended Posts

Hello,
I hope someone of you knows the label propagation algorithm?
It is used on networks /graphs to find clusters/communities.
In the first step, every node in the graph gets a unique label.
In the next step, the labels of the nodes are replaced by a label that most of its neighbors have.
The algorithms is described in https://arxiv.org/pdf/0709.2938.pdf on page 5.

I wonder if it works only on undirected graphs or even directed graphs.
If it also works on directed graphs, when is one node a neighbor of another?
In other words, if two nodes A and B are connected by a directed edge A --> B, which node is
neighbor of which?
Is only node B a neighbor of A, because it has a connection to B, but not vice versa?

What do you think?

Thanks in advance

Share this post


Link to post
Share on other sites

Thank you very much, the lecture is very interesting.

Maybe you allow me another question. Can you recommend an algorithm that would be suitable for calculating the modularity of directed graphs if they are already subdivided into communities? I know only the method of Newman which is applied to undirected partitioned graphs.

Thanks in advance

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now