Page 1 of 1

How does Label propagation algorithm works on directed graphs?

Posted 26 November 2017 - 06:11 AM

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?

Is This A Good Question/Topic? 0

Replies To: How does Label propagation algorithm works on directed graphs?

#2 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12648
• Posts: 45,822
• Joined: 27-December 08

Re: How does Label propagation algorithm works on directed graphs?

Posted 26 November 2017 - 10:14 AM

Moved to Computer Science.

I glanced at the paper and didn't see any place where the undirected assumption is being used. In theory, the algorithm should work fine for directed graphs.

In directed graphs, we say that B is a neighbor of A if the edge A -> B is in the graph.

Re: How does Label propagation algorithm works on directed graphs?

Posted 26 November 2017 - 11:54 AM

ok, Thank you.
This would mean, for a directed edge A --> B, that while B is a neighbor of A,
A ist not a neighbor of B.
Therefore, considering the label propagation algorithm, if just a new label were assigned to node B, the label of A would not be counted for B. Conversely, if A were to be assigned a new label, the label of B would be counted.
Do I understand this in the right manner?

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }