Jump to content

How does Label propagation algorithm works on directed graphs?


Code Now

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

Link to comment
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

Link to comment
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
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.