Skip to content

Latest commit

 

History

History
114 lines (87 loc) · 2.46 KB

README.md

File metadata and controls

114 lines (87 loc) · 2.46 KB
Raw

Infomap

2021.12.12

Reference

  • Multilevel Compression of Random Walks on Networks Reveals Hierarchical Organization in Large Integrated Systems
  • Ranking and clustering of nodes in networks with smart teleportation
  • Measuring Scholarly Impact Methods and Practice, Chapter. 1: Community detection and visualization of networks with the map equation framework

Notations

Flows

  • pagerank = $p_{\alpha}^*$
  • linkFlow = $q_{\alpha \curvearrowright \beta}$
  • nodeFlow = $p_{\alpha}$

CodeLength

  • module flows
    • enterFlow to j = $q_{j \curvearrowleft}$
    • exitFlow to i = $q_{i \curvearrowright}$
    • totalFlow of i = $p_{i \circlearrowright}$
  • code length
    • moduleCodeLength = $q_{\curvearrowleft}H(Q)$
    • indexCodeLength of module i = $p_{i \circlearrowright}H(P^i)$

Structs (write only member variables)

directed link with weight

struct Link
{
	int source;
	int target;
	double weight;
};

flows w.r.t pagerank with unrecorded link teleportation

struct FlowData
{
	vector<Link> links;
	vector<Link> nlinks; // links normalized by outflows
	vector<Link> linkFlows;
	vector<vector<Link>> adj_outLinkFlows; // adjacency list of outlinkFlows
	vector<vector<Link>> adj_inLinkFlows;  // adjacency list of  inlinkFlows
	vector<double> nodeFlows;
};

code length

struct CodeLength
{
	double L;
	double moduleCodeLength;
	vector<double> indexCodeLength;
	vector<double> enterFlows; // for module Code
	vector<double> exitFlows;  // for index Code
	vector<double> totalFlows; // for index Code
};

community

struct Community
{
	int N;
	FlowData flowdata;
	double tau;
	vector<int> n2c; // community indices for each node
	CodeLength code;
};

delta code length

struct DeltaCodeLength
{
	int targetModule;
	double delta_codeLength;
	CodeLength new_code;
};

Notes

Node probabilities

  • pagerank with unrecorded link teleportation を使用．
  • ノードへの転移確率を outflow の比で与えたページランクをべき乗法で計算した後，リンクに沿った遷移のみを抽出する．
  • パラメータ
    • max_iter = 100
    • tau = 0.15 (teleportation ratio)

Optimization

  1. 全ノードをシャッフルし，各 1 回ずつ最適ノードを探索する．

  2. 1 を 3 回行って更新がなければ収束したものとみなす．

  3. 1 の最大反復数はノード数 N とした．

  4. NC の更新は reindex のときのみ

Aggregation

  • 自己ループを含める