Eigenvector Centrality Algorithm

Eigenvector centrality is an established measure of global connectivity, from which the importance and influence of nodes can be inferred. Eigenvector centrality quantifies a node's influence within a graph. A node's importance is determined by its neighbors—it is both influenced by them and exerts influence on them. However, not all connections are equal; a node's centrality increases if it is connected to other highly influential nodes. In short, Eigenvector centrality gets the centrality of the vertices in an intricate way using neighbors, allowing to find well-connected vertices.

  

 Let's start by creating some sample data:

 

    create table website (website_url varchar(50));
    create table links(link_from varchar(50), link_to varchar(50), weight float);

    insert into website values ('web1')
    , ('web2')
    , ('web3')
    , ('web4')
    , ('web5')
    , ('web6');

    insert into links values ('web1', 'web1', .2),
        ('web1', 'web2', .3),
        ('web2', 'web3', .4),
        ('web3', 'web1', .4),
        ('web3', 'web2', .4),
        ('web3', 'web4', .4),
        ('web3', 'web5', .4),
        ('web5', 'web3', .4),
        ('web6', 'web6', .4);

Next create a PROPERTY GRAPH to represent Web Graph

CREATE OR REPLACE PROPERTY GRAPH web_graph
  VERTEX TABLES (
    website KEY (website_url) PROPERTIES ARE ALL COLUMNS
  )
  EDGE TABLES ( 
    links
      key (link_from, link_to) 
      SOURCE KEY (link_from) REFERENCES website(website_url)
      DESTINATION KEY(link_to) REFERENCES website(website_url)
      PROPERTIES ARE ALL COLUMNS
    
);

You can use the following SQL/PGQ to query the above PROPERTY GRAPH

SELECT distinct 
   website_a
   , website_b
   , v1
   , v2
   , e1
FROM GRAPH_TABLE (
       web_graph
       MATCH   (link_from  IS website) - [e is links] -> (link_to is website)
       COLUMNS (
               link_from.website_url  as website_a
               , link_to.website_url  as website_b
               --, e_path.relationship as e_path_relationship
               , vertex_id(link_from) as v1
               , vertex_id(link_to) as v2
               , edge_id(e) as e1

        )
);

Finally run eigenvector_centrality algorithm on the above PROPERTY GRAPH

%python-pgx


print(session)

# Write your codeprint(session)
graph = session.read_graph_by_name("WEB_GRAPH", "pg_sql")
print(graph)
analyst.pagerank(graph)
analyst.degree_centrality(graph)
analyst.in_degree_centrality(graph)
analyst.out_degree_centrality(graph)
analyst.vertex_betweenness_centrality(graph)
analyst.local_clustering_coefficient(graph)
analyst.eigenvector_centrality(graph)
analyst.communities_label_propagation(graph, 100, 'label_propagation')

print(cycle)
graph.query_pgql("""
SELECT 
  a.website_url
  , a.eigenvector
  , a.label_propagation
FROM MATCH (a)
""").print()

Output:

PgxSession(id: 5ef30734-4ebb-4f22-87fe-457c3e5ccc84, name: ADMIN)
PgxGraph(name: WEB_GRAPH, v: 6, e: 9, directed: True, memory(Mb): 0)
PgxPath(graph: WEB_GRAPH, src: PgxVertex[provider=WEBSITE,key=web1,ID=WEBSITE(web1)], dst: PgxVertex[provider=WEBSITE,key=web1,ID=WEBSITE(web1)], num. edges: 1 cost: 1.0)
+---------------------------------------------------------+
| website_url | eigenvector           | label_propagation |
+---------------------------------------------------------+
| web1        | 0.24693143869692635   | 0                 |
| web2        | 0.19814795883595723   | 1                 |
| web3        | 0.3567709398214408    | 1                 |
| web4        | 0.0                   | 1                 |
| web5        | 0.19814795883595723   | 1                 |
| web6        | 1.7038097185306344E-6 | 2                 |
+---------------------------------------------------------+