May i calculate betweenness centrality of community?

Neo4j Graph Platform Graph Algorithms/Graph Data Science
1

I need to find intermediate communities. Is it possible to define a community as a node and find out which community is a bridge between other communities?

2

What do you mean by 'intermediate communities'? The Louvain algorithm includes an option to include intermediate communities (meaning, smaller communities that were merged during the modularity optimization process) -- just set includeIntermediateCommunities:true in the configuration.

We don't currently offer algorithms that create overlapping communities, so each node belongs to a single community. What you could do is create nodes representing each unique community, and create an edge between each node that belongs in that community and the community node (basically, create a new Community node for each community ID found, and then add a MEMBER_OF relationship for each node with that community ID). Then you can use cypher to find nodes that belong in one community, but have a relationship with a node in a different community -- something like

MATCH (c1:Community)<-[:MEMBER_OF]-(n1:Node)-[]-(n2:Node)-[:MEMBER_OF]->(c2:Community)
WHERE c1.id <> c2.id
RETURN n1, n2

Or, you could modify it to look for communities with nodes in two different communities:

MATCH (c1:Community)<-[:MEMBER_OF]-(n1:Node)-[]-(n2:Node)-[:MEMBER_OF]->(c2:Community)<-[:MEMBER_OF]-(n3:Node)-[]-(n4:Node)-[:MEMBER_OF]->(c3:Community)
WHERE c1.id <> c2.id AND c1.id<>c3.id AND c2.id<>c3.id
RETURN c2.id as bridge_community
2 Likes
3

Thanks for the great answer, this is useful information, but i need to find a community that serves as a bridge between other communities.

4

Yes. The second cypher query I provided you is the closest thing we offer --

MATCH (c1:Community)<-[:MEMBER_OF]-(n1:Node)-[]-(n2:Node)-[:MEMBER_OF]->(c2:Community)<-[:MEMBER_OF]-(n3:Node)-[]-(n4:Node)-[:MEMBER_OF]->(c3:Community)
WHERE c1.id <> c2.id AND c1.id<>c3.id AND c2.id<>c3.id
RETURN c2.id as bridge_community

C2 has nodes with edges to nodes in C1 and C3. You could add weights, based on how many edges there are between C2 nodes and C1/C3 nodes, etc.

We don't offer any sort of community betweenness centrality out of the box. You could construct a community node graph -- basically what I already explained -- and construct edges between and communities based on a node in one community having a relationship with a node in another community, and use the number of neighbor nodes as weights. You could then run betweenness centrality over this graph and use the score assigned to the communities as the result.

2 Likes
5

Thanks for the very detailed explanation

6

What will be the syntax for the GDS library ?

i tried this code

CALL gds.graph.create.cypher(
  'bridge',
  'MATCH (u:user) RETURN id(u) AS id
   UNION 
   MATCH (c:Community) RETURN id(c) AS id',
  'MATCH (c1:Community)<-[:MEMBER_OF]-(u1:user)-[]-(u2:user)-[:MEMBER_OF]->(c2:Community)<-[:MEMBER_OF]-(u3:user)-[]-(u4:user)-[:MEMBER_OF]->(c3:Community)
   WHERE c1.id <> c2.id AND c1.id<>c3.id AND c2.id<>c3.id
   RETURN id(c1) AS source, id(c2) AS bridge_community, id(c3) AS target'
)

but i get a projection of the entire database instead of the path i need

I understand that there is no weights in GDS betweenness centrality. Is that make sense to search bridge community without using weights?

Thank for your time and attention :slightly_smiling_face: