HANP¶

Algorithm introduction¶

HANP performs weighted label propagation with neighborhood influence to detect communities.

Run a classic weighted undirected HANP community detection pass. Each node starts with its own id as the label, neighbor votes are weighted by edge weight, degree^preference_exponent, and attenuated label score, and the procedure returns the last partition reached within max_iter rounds.

For more information, see HANP.

Data model¶

To implement the HANP algorithm in GQL, the following data model is used to create a graph type:

Entities are represented by nodes of type Node, with properties id and rating.
Relationships are represented by edges of type Link, with property weight.

For the complete definition of the graph type, see Prepare graph data.

Procedure implementation ¶

To compute HANP results, a procedure is created.

For more information about the procedure, see Procedure implementation. The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

max_iter: INT64 (default: 20). Maximum number of label propagation iterations.
hop_decay: DOUBLE (default: 0.1). Decay factor applied to the preference score per hop (0 < hop_decay <= 1).
preference_exponent: DOUBLE (default: 1.0). Exponent used to weight the neighbor preference score influence.

Additionally, the following variables are defined within the procedure:

Variable name	Variable type	Description
`iter`	Primitive value variable	Current iteration counter.
`changed`	Primitive value variable	Whether any node label changed in this iteration.
`degree`	Node-attached SumAgg aggregator value variable	Per-node degree, used for preference score normalization.
`label`	Node-attached SumAgg aggregator value variable	Per-node current community label.
`next_label`	Node-attached SumAgg aggregator value variable	Per-node candidate label for the next iteration.
`score`	Node-attached SumAgg aggregator value variable	Per-node preference score indicating label stability.
`next_score`	Node-attached SumAgg aggregator value variable	Per-node preference score for the next iteration.
`support`	Node-attached SumAgg aggregator value variable	Per-node map of {label → weighted vote sum} from neighbors.
`prop`	Node-attached SumAgg aggregator value variable	Per-node map of {label → max preference score} from neighbors.
`result_table`	Table variable	Output table storing (vertex_id, label) pairs.

The following steps outline the logic of the procedure:

Initialize each node's label from its rating property, and score to 1.0; compute degree.
Iterate: for each node, collect neighbor labels weighted by edge weight and neighbor preference scores into support and prop.
Select the label with the highest weighted support as next_label; decay next_score by 1 / degree.
Apply updates to label and score; stop when no label changes or max_iter is reached. Return (vertex_id, label).

Steps¶

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow Prepare algorithm sample data to check where to run commands and how the directory is mounted.

1. Prepare graph data ¶

Create a graph type that matches your data model.

'''
CREATE GRAPH TYPE IF NOT EXISTS hanp_graph_type AS {
    NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
    EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
}
'''

Download these CSV files and save them with their original names in examples/algorithms/hanp/ under your deployment directory:

hanp_node.csv: Node data.
hanp_edge.csv: Edge data.

Preview the CSV files

hanp_node.csv

id,rating
1,0
2,2
3,1
4,0
5,0
6,2
7,1
8,2
9,0
10,1
11,0
12,2
13,1
14,1
15,0
16,2
17,0
18,1
19,2
20,0
21,2
22,1
23,0
24,1

hanp_edge.csv

src_id,dst_id,weight
1,2,4
1,3,2
1,4,7
1,5,9
2,3,1
2,4,6
2,5,5
2,6,2
3,4,3
3,5,4
3,6,8
4,6,2
4,7,6
4,8,5
5,6,4
5,8,7
5,9,6
6,8,1
6,9,5
6,10,6
7,9,2
7,10,9
8,9,3
8,11,6
8,12,4
9,10,4
9,12,7
9,13,2
10,12,1
10,13,8
10,14,4
11,12,2
11,14,5
11,15,7
12,14,3
12,15,6
12,16,5
13,15,2
13,16,7
14,15,4
14,17,8
14,18,2
15,16,1
15,18,5
15,19,3
16,18,3
16,19,6
17,18,2
17,20,7
17,21,5
18,19,4
18,21,9
18,22,6
19,21,1
19,22,5
20,21,3
20,23,6
20,24,8
21,22,2
21,23,4
21,24,7
22,24,4
23,24,1

Create a temporary graph based on the graph type and load the data files into the temporary graph.

CREATE TEMPORARY GRAPH IF NOT EXISTS #hanp_graph TYPED hanp_graph_type

'''
USE #hanp_graph IMPORT INTO GRAPH {
      NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
          PATH: "file:///examples/algorithms/hanp/hanp_node.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      },
      EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
          PATH: "file:///examples/algorithms/hanp/hanp_edge.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      }
  }
'''

After the import succeeds, run this query in the console to check the node count:

'''
USE #hanp_graph
MATCH (n)
RETURN count(n) AS node_count
'''

The expected node_count is 24. If it differs, check the files and import results before continuing.

2. Create a procedure ¶

Create a procedure to implement the HANP algorithm. For more information about the procedure, see Procedure implementation.

'''
CREATE OR REPLACE PROCEDURE hanp(
  max_iter INT64 DEFAULT 20,
  hop_decay DOUBLE DEFAULT 0.1,
  preference_exponent DOUBLE DEFAULT 1.0
)
RETURNS (vertex_id INT64, community_id INT64, label_score DOUBLE)
COMMENT "Run a classic weighted undirected HANP community detection pass. Each vertex starts with its own id as the label, neighbor votes are weighted by edge weight, degree^preference_exponent, and attenuated label score, and the procedure returns the last partition reached within max_iter rounds."
AS {
  VALUE iter INT64 = 0
  VALUE changed OrAgg = true

  NODE VALUE degree SumAgg<INT64> = 0
  NODE VALUE label SumAgg<INT64> = 0
  NODE VALUE next_label SumAgg<INT64> = 0
  NODE VALUE score SumAgg<DOUBLE> = 1.0
  NODE VALUE next_score SumAgg<DOUBLE> = 1.0
  NODE VALUE support MapAgg<INT64, SumAgg<DOUBLE>>
  NODE VALUE prop MapAgg<INT64, MaxAgg<DOUBLE>>

  TABLE result_table TYPED TABLE {
    vertex_id INT64,
    community_id INT64,
    label_score DOUBLE
  }

  MATCH (n)
  PER NODE (n) {
    SET n.@degree = 0
    SET n.@label = n.id
    SET n.@next_label = n.id
    SET n.@score = 1.0
    SET n.@next_score = 1.0
    SET n.@support.clear()
    SET n.@prop.clear()
  }

  MATCH (s)-[e]-(t)
  PER PATH {
    SET s.@degree += 1
  }

  WHILE @changed AND iter < max_iter THEN {
    SET iter = iter + 1
    SET @changed = false

    MATCH (n)
    PER NODE (n) {
      SET n.@next_label = n.@label
      SET n.@next_score = n.@score
      SET n.@support.clear()
      SET n.@prop.clear()
    }

    MATCH (s)-[e]-(t)
    PER PATH {
      VALUE propagated DOUBLE = 0.0
      VALUE preference DOUBLE = 1.0

      SET propagated = t.@score - hop_decay

      IF propagated < 0.0 THEN {
        SET propagated = 0.0
      }

      IF t.@degree > 0 THEN {
        SET preference = exp(preference_exponent * ln(CAST(t.@degree AS DOUBLE)))
      }

      SET s.@support += TUPLE(t.@label, preference * propagated * CAST(e.weight AS DOUBLE))
      SET s.@prop += TUPLE(t.@label, propagated)
    }

    MATCH (s)
    WHERE s.@support.size() > 0
    PER NODE (s) {
      VALUE idx INT64 = 0
      VALUE cand_label INT64 = 0
      VALUE cand_support DOUBLE = 0.0
      VALUE cand_prop DOUBLE = 0.0
      VALUE best_label INT64 = s.@label
      VALUE best_support DOUBLE = -1.0
      VALUE best_prop DOUBLE = s.@score

      WHILE idx < s.@support.size() THEN {
        SET cand_label = (s.@support[idx])._0
        SET cand_support = (s.@support[idx])._1
        SET cand_prop = s.@prop.get(cand_label)

        IF cand_support > best_support
          OR (cand_support = best_support AND cand_prop > best_prop)
          OR (cand_support = best_support AND cand_prop = best_prop AND cand_label < best_label) THEN {
          SET best_label = cand_label
          SET best_support = cand_support
          SET best_prop = cand_prop
        }

        SET idx = idx + 1
      }

      SET s.@next_label = best_label
      SET s.@next_score = best_prop
    }

    MATCH (n)
    PER NODE (n) {
      IF n.@next_label <> n.@label THEN {
        SET @changed += true
      }

      SET n.@label = n.@next_label
      SET n.@score = n.@next_score
    }
  }

  MATCH (n)
  PER NODE (n) {
    EXPORT n.id, n.@label, n.@score INTO result_table
  }

  FOR r IN result_table
  RETURN
    r.vertex_id AS vertex_id,
    r.community_id AS community_id,
    r.label_score AS label_score
  ORDER BY vertex_id ASC
}
'''

3. Call your procedure ¶

Use the procedure defaults to find communities, returning each node's community ID and label score.

USE #hanp_graph CALL hanp() RETURN vertex_id, community_id, label_score

Returns:

Expand to view results

+-----------+--------------+-------------+
| vertex_id | community_id | label_score |
+-----------+--------------+-------------+
| 1         | 3            | 0.0         |
| 2         | 3            | 0.0         |
| 3         | 3            | 0.0         |
| 4         | 3            | 0.0         |
| 5         | 3            | 0.0         |
| 6         | 3            | 0.0         |
| 7         | 3            | 0.0         |
| 8         | 3            | 0.0         |
| 9         | 3            | 0.0         |
| 10        | 3            | 0.0         |
| 11        | 3            | 0.0         |
| 12        | 3            | 0.0         |
| 13        | 3            | 0.0         |
| 14        | 3            | 0.0         |
| 15        | 3            | 0.0         |
| 16        | 3            | 0.0         |
| 17        | 3            | 0.0         |
| 18        | 3            | 0.0         |
| 19        | 3            | 0.0         |
| 20        | 3            | 0.0         |
| 21        | 3            | 0.0         |
| 22        | 3            | 0.0         |
| 23        | 3            | 0.0         |
| 24        | 3            | 0.0         |
+-----------+--------------+-------------+

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see EXPORT. Match the exported fields to the returned columns and target properties.

HANP¶

Algorithm introduction¶

Data model¶

Procedure implementation¶

Steps¶

1. Prepare graph data¶

2. Create a procedure¶

3. Call your procedure¶

Procedure implementation ¶

1. Prepare graph data ¶

2. Create a procedure ¶

3. Call your procedure ¶