Статьи

Neo4j: процедура для алгоритма кластеризации SLM

Февраль 16, 2019

В середине прошлого года я писал в блоге об алгоритме Smart Local Moving, который используется для обнаружения сообщества в сетях, и с предстоящим внедрением процедур в Neo4j, я подумал, что было бы интересно сделать этот код доступным как единое целое.

Если вы хотите взять код и следовать ему, он находится в репозитории SLM на моем github .

На данный момент процедура жестко запрограммирована для работы с отношениями KNOWS между двумя узлами, но это можно легко изменить.

Чтобы проверить, работает ли он правильно, я подумал, что было бы разумнее использовать набор данных Каратэ-клуба, описанный на домашней странице SLM . Я думаю, что этот набор данных изначально из сетей, толп и рынков .

Я написал следующий скрипт CSV LOAD для создания графика в Neo4j:

1
2
3
4
5
LOAD CSV FROM "file:///Users/markneedham/projects/slm/karate_club_network.txt" as row
FIELDTERMINATOR "\t"
MERGE (person1:Person {id: row[0]})
MERGE (person2:Person {id: row[1]})
MERGE (person1)-[:KNOWS]->(person2)

график

Затем нам нужно вызвать процедуру, которая добавит соответствующую метку каждому узлу в зависимости от того, к какому сообществу он принадлежит. Вот как выглядит код процедуры:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class ClusterAllTheThings
{
    @Context
    public org.neo4j.graphdb.GraphDatabaseService db;
  
    @Procedure
    @PerformsWrites
    public Stream<Cluster> knows() throws IOException
    {
        String query = "MATCH (person1:Person)-[r:KNOWS]->(person2:Person) \n" +
                       "RETURN person1.id AS p1, person2.id AS p2, toFloat(1) AS weight";
  
        Result rows = db.execute( query );
  
        ModularityOptimizer.ModularityFunction modularityFunction = ModularityOptimizer.ModularityFunction.Standard;
        Network network = Network.create( modularityFunction, rows );
  
        double resolution = 1.0;
        int nRandomStarts = 1;
        int nIterations = 10;
        long randomSeed = 0;
  
        double modularity;
  
        Random random = new Random( randomSeed );
  
        double resolution2 = modularityFunction.resolution( resolution, network );
  
        Map<Integer, Node> cluster = new HashMap<>();
        double maxModularity = Double.NEGATIVE_INFINITY;
  
        for ( int randomStart = 0; randomStart < nRandomStarts; randomStart++ )
        {
            network.initSingletonClusters();
  
            int iteration = 0;
            do
            {
                network.runSmartLocalMovingAlgorithm( resolution2, random );
                iteration++;
  
                modularity = network.calcQualityFunction( resolution2 );
            } while ( (iteration < nIterations) );
  
            if ( modularity > maxModularity )
            {
                network.orderClustersByNNodes();
                cluster = network.getNodes();
                maxModularity = modularity;
            }
        }
  
        for ( Map.Entry<Integer, Node> entry : cluster.entrySet() )
        {
            Map<String, Object> params = new HashMap<>();
            params.put("userId", String.valueOf(entry.getKey()));
  
            db.execute("MATCH (person:Person {id: {userId}})\n" +
                       "SET person:`" + (format( "Community-%d`", entry.getValue().getCluster() )),
                    params);
        }
  
        return cluster
                .entrySet()
                .stream()
                .map( ( entry ) -> new Cluster( entry.getKey(), entry.getValue().getCluster() ) );
    }
  
    public static class Cluster
    {
        public long id;
        public long clusterId;
  
        public Cluster( int id, int clusterId )
        {
            this.id = id;
            this.clusterId = clusterId;
        }
    }
}

Я жестко запрограммировал некоторые параметры, чтобы использовать значения по умолчанию, которые могут быть раскрыты с помощью процедуры, чтобы обеспечить больший контроль при необходимости. Функция Network # create предполагает, что она получит поток строк, содержащих столбцы «p1», «p2» и «weight» для представления «source», «destination» и «weight» отношений между ними.

Мы называем процедуру так:

1
CALL org.neo4j.slm.knows()

Он вернет каждый из узлов и кластер, которому он был назначен, и если мы затем визуализируем сеть в браузере neo4j, мы увидим это:

граф-1

что похоже на визуализацию с домашней страницы SLM:

сеть

Если вы хотите поиграть с кодом, не стесняйтесь. Вам нужно будет выполнить следующие команды, чтобы создать JAR для плагина и развернуть его.

1
2
3
$ mvn clean package
$ cp target/slm-1.0.jar /path/to/neo4j/plugins/
$ ./path/to/neo4j/bin/neo4j restart

И вам понадобится последняя веха Neo4j, в которой включены процедуры.

Ссылка: Neo4j: процедура для алгоритма кластеризации SLM от нашего партнера JCG Марка Нидхэма в блоге Марка Нидхэма .
43
Share: