---
title: "Influence Maximization"
description: "Overview of TigerGraph's Influence Maximization algorithm."
component: "graph-ml"
version: "3.10"
module: "centrality-algorithms"
html_url: "/graph-ml/3.10/centrality-algorithms/influence-maximization"
canonical_url: "https://www.tigergraph.com/docs/graph-ml/3.10/centrality-algorithms/influence-maximization"
markdown_url: "https://www.tigergraph.com/docs/graph-ml/3.10/centrality-algorithms/influence-maximization.md"
---

[View as HTML](https://www.tigergraph.com/docs/graph-ml/3.10/centrality-algorithms/influence-maximization)

# Influence Maximization

Supported Graph Characteristics

| Weighted edges |
| --- |
| Unweighted edges |
| Homogeneous vertex types |

Algorithm links: [Influence Maximization](https://github.com/tigergraph/gsql-graph-algorithms/tree/master/algorithms/Centrality/influence%5Fmaximization)

Influence maximization is the problem of finding a small subset of vertices in a social network that could maximize the spread of influence. There are two versions of the Influence Maximization algorithm. Both versions find k vertices that maximize the expected spread of influence in the network. The CELF version improves upon the efficiency of the greedy version and should be preferred in analyzing large networks.

## Notes

The algorithm is implemented based on the following research papers:

* CELF: [Cost-effective Outbreak Detection in Networks](https://www.cs.cmu.edu/~jure/pubs/detect-kdd07.pdf)
* Greedy: [Maximizing the Spread of Influence through a Social Network](https://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf)

## Specifications

CELF

```gsql
CREATE QUERY tg_influence_maximization_CELF(STRING v_type,STRING e_type, STRING weight_attribute, INT top_k, BOOL print_results = True, STRING file_path = "")
```

Greedy

```gsql
CREATE QUERY tg_influence_maximization_greedy(STRING v_type,
  STRING e_type,STRING weight_attribute,INT top_k,
  BOOL print_results = True, STRING file_path = "")
```

### Parameters

The CELF version and the greedy version of the algorithms share the same set of parameters.

| Name | Description |
| --- | --- |
| `STRING v_type` | The vertex type to measure influence of |
| `STRING e_type` | The edge type to traverse |
| `STRING weight_attribute` | The name of the weight attribute on the edge type |
| `INT top_k` | The number of vertices with the highest influence score to return |
| `BOOL print_results` | If true, print results to JSON output. |
| `STRING file_path` | If not empty, save results in CSV to this file. |

### Output

Returns the ID of the vertices with the highest influence scores along with their scores.

### Time complexity

The greedy version has a complexity of \\(O(E \* k)\\), where \\(E\\) is the number of edges and \\(k\\) is the number of top scores to report.

The CELF version also has a worst-case complexity of \\(O(E \* k)\\), but generally performs much better with a best-case complexity of \\(O(E)\\).

## Examples

We use this example graph showing a social network.

![social graph 2022 10](https://www.tigergraph.com/docs/graph-ml/3.10/centrality-algorithms/_images/social-graph-2022-10.png) 

### CELF

```json
[
  {
    "@@res_list": [
      {
        "Vertex_ID": "Dan",
        "score": 4
      },
      {
        "Vertex_ID": "Vicki",
        "score": 3
      },
      {
        "Vertex_ID": "Nancy",
        "score": 2
      },
      {
        "Vertex_ID": "Juan",
        "score": 1
      },
      {
        "Vertex_ID": "Kevin",
        "score": 1
      },

    ]
  }
]
```

### Greedy

```json
[
  {
    "@@res_list": [
      {
        "Vertex_ID": "Dan",
        "score": 4
      },
      {
        "Vertex_ID": "Nancy",
        "score": 3
      },
      {
        "Vertex_ID": "Vicki",
        "score": 2
      },
      {
        "Vertex_ID": "Juan",
        "score": 1
      },
      {
        "Vertex_ID": "Jenny",
        "score": 1
      },
    ]
  }
]
```
