Skip to content
Demo codes for fast von Neumann graph entropy computation method published at ICML 2019
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
GraEntExact.m
README.md
VNGE_FINGER.m
main_FINGER_demo.m

README.md

FINGER: Fast Incremental von Neumann Graph Entropy Computation

MATLAB demo codes for fast von Neumann graph entropy computation method published at ICML 2019

Paper link: https://arxiv.org/abs/1805.11769

Authors: Pin-Yu Chen, Lingfei Wu, Sijia Liu, Indika Rajapakse

Environment: tested on MATLAB R2016b

Demo: compute von Newmann graph entropy (VNGE) using FINGER (FAST)

  1. Run main_FINGER_demo.m
  2. The demo code first generates a Erdos-Renyi graph with n nodes and n*p average degree. Its connectivity pattern is characterized by the adjacency matrix A
  3. GraEntExact(A) computes the exact VNGE of A and reports the computation time
  4. VNGE_FINGER(A) uses FINGER (FAST) to compute the approximate VNGE of A and report the computation time
  5. The demo code also shows the scaled appromimation error (SAE) and computation time reduction ratio (CTRR)

Sample results using n=10^4 and p=10^-2

Computing exact VNGE takes 37.6566 seconds

Computing VNGE using FINGER (FAST) takes 0.35195 seconds

The computation time reduction ratio is 99.0654%

The scaled appromimation error is 0.039722

You can’t perform that action at this time.