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

## 2 Replies - 725 Views - Last Post: 26 November 2017 - 11:54 AM

### #1

# How does Label propagation algorithm works on directed graphs?

Posted 26 November 2017 - 06:11 AM

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

### #2

## 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.

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.

### #3

## 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?

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