neo4j-contrib / neo4j-graph-algorithms

Efficient Graph Algorithms for Neo4j
https://github.com/neo4j/graph-data-science/
GNU General Public License v3.0
769 stars 195 forks source link

Support directed local clustering coefficient #844

Open szarnyasg opened 5 years ago

szarnyasg commented 5 years ago

I am working to implement the LDBC Graphalytics workload using the Graph algorithms library. This requires implementing the directed variant of the local clustering coefficient (LCC).

The specification defines the LCC graph metric similarly to the definition in Wikipedia:

image

The important thing to consider is that edges that go directions are only considered between the neighbours, the neighbours of a given node are considered without taking directions into account.

Example graph, based on the lcc/dir-input and the lcc/dir-output files:

image

A smaller subgraph:

image

It's worth noting that most graphs in the basic Graphalytics data set are undirected with the exception of the following ones:

config-template/graphs$ ag 'directed = true'
twitter_mpi.properties
13:graph.twitter_mpi.directed = true

wiki-Talk.properties
13:graph.wiki-Talk.directed = true

example-directed.properties
12:graph.example-directed.directed = true

cit-Patents.properties
13:graph.cit-Patents.directed = true