CohesiveSubgraph

A Python library to compute Cohesive subgraphs on NetworkX graph.

This work computes Core-based, Triangle-based, Clique-based, connected-component based, and other approaches.

CORE-BASED APPROACHES

• $k$-core [1]
• $(k,s)$-core [2]
• $(k,h)$-core [3]
• $(k,p)$-core [4]
• $k$-peak [5]

TRIANGLE-BASED APPROACHES

• $k$-truss [6]
• $k$-tripeak [7]

CLIQUE-BASED APPROACHES

• $k$-distance clique [8]
• max $k$-clique [8]
• $k$-clan [9]
• $k$-club [9]

CONNECTED-COMPONENT BASED APPROACHES

• $k$-VCC($k$-vertex connected component) [13]
• $k$-ECC($k$-edge connected component) [14]

OTHER APPROACHES

• Alphacore [15]
• $k$-core-truss [16]

---

Parameter Setting & Result

Parameter Settings

Algorithms	parameter	example
$k$-core	$k$=3	simple toy network
$(k,s)$-core	$k$ = 3, $s$ = 2	[2] Fig. 2.
$(k,h)$-core	$k$ = 5, $h$ = 2	[3] Fig. 1.
$(k,p)$-core	$k$ = 3, $p$ = 0.5	[4] Fig. 1.
$k$-peak	$k$ = 3	simple toy network
$k$-truss	$k$ = 4	simple toy network
$k$-tripeak	$k$ = 4	[7] Fig. 2.
max $k$-clique	$k$ = 5	simple toy network 2
$k$-distance clique	$k$ = 2	simple toy network 2
$k$-VCC	$k$ = 3	simple toy network
$k$-ECC	$k$ = 5	simple toy network
Alphacore	$\alpha$ = 0.1	simple toy network
$k$-core-truss	$k$=3, $\alpha$ = 1	[16] Fig. 2.

Result

The plot of the results of the previous parameter setting is shown.

$k$-core	($k,s$-core)	($k,h$)-core
($k,p$)-core	$k$-peak	$k$-truss
$k$-tripeak	max $k$-clique	$k$-VCC
$k$-ECC	Alphacore	$k$-core-truss
$k$-distance clique 1	$k$-distance clique 2

$k$-distance clique has two answers.

$k$-distance clique
Answer 1	Answer 2

---

Package Requirements

• python = 3.8
• networkx = 2.7.1
• pandas = 1.1.3
• scipy = 1.4.1

---

Getting started

Clone repo and install requirements.txt

git clone https://github.com/cscnudi/CohesiveSubgraph
cd CohesiveSubgraph
pip install -r requirements.txt

How to use

• Usage Using the algorithm files under the css folder. This is a simple example.

import networkx as nx
from css import alg_kcore,alg_alphacore, alg_kecc, alg_khcore, alg_kpcore, alg_kpeak, alg_kscore, alg_ktruss, alg_kvcc
from css import alg_kdistance_clique, alg_ksize_clique, alg_ktripeak, alg_alg_kcoretruss, common_utility

G = nx.karate_club_graph() # input graph

C = alg_kcore.run(G, k=3) # run k-core 
common_utility.print_result(G, C)

C = alg_kscore.run(G, k=3,s=2) # run (k,s)-core 
common_utility.print_result(G, C)

C = alg_khcore.run(G, k=5, h=2) # run (k,h)-core
common_utility.print_result(G, C)

C = alg_kpcore.run(G, k=3,p=0.5) # run (k,p)-core 
common_utility.print_result(G, C)

C = alg_kpeak.run(G, k=3) # run k-peak 
common_utility.print_result(G, C)

C = alg_ktruss.run(G, k=4) # run k-truss
common_utility.print_result(G, C)

C = alg_ktripeak.run(G, k=4) # run k-tripeak
common_utility.print_result(G, C)

C = alg_ksize_clique.run(G, k=5) # max k-clique
common_utility.print_result(G, C)

C = alg_kdistance_clique.run(G, k=5) # run k-distance clique
common_utility.print_result(G, C)

C = alg_kvcc.run(G, k=3) # run k-VCC
common_utility.print_result(G, C)

C = alg_kecc.run(G, k=5) # run k-ECC
common_utility.print_result(G, C)

C = alg_alphacore.run(G, alpha=0.1) # run Alphacore
common_utility.print_result(G, C)

C = alg_kcoretruss.run(G, k=5, alpha=1) # run k-core-truss
common_utility.print_result(G, C)

• run file usage

Using the run file under the css folder.

• Run test file

Go to test folder and run.

python kcore_test.py # run k-core
			--k 3  # parameter k value
			--network example.dat  # network edges file

python kscore_test.py # run (k,s)-core
			--k 3  # parameter k value
			--s 2  # parameter s value
			--network example.dat  # network edges file

python khcore_test.py # run (k,h)-core
			--k 5  # parameter k value
			--h 2  # parameter h value
			--network example.dat  # network edges file

python kpcore_test.py # run (k,p)-core
			--k 3  # parameter k value
			--p 0.5  # parameter h value
			--network example.dat  # network edges file

python kpeak_test.py # run k-peak
			--k 3  # parameter k value
			--network example.dat  # network edges file

python ktruss_test.py # run k-truss
			--k 4  # parameter k value
			--network example.dat  # network edges file

python ktripeak_test.py # run k-tripeak
			--k 4  # parameter k value
			--network example.dat  # network edges file

python ksize_clique_test.py # run max k-clique
			--k 5  # parameter k value
			--network example.dat  # network edges file

python kdistance_clique_test.py # run max k-clique
			--k 5  # parameter k value
			--network example.dat  # network edges file

python kvcc_test.py # run k-VCC
			--k 3  # parameter k value
			--network example.dat  # network edges file

python kecc_test.py # run k-ECC
			--k 5  # parameter k value
			--network example.dat  # network edges file

python alphacore_test.py # run Alphacore
			--alpha 0.1  # parameter alpha value						
			--network example.dat  # network edges file

python kcoretruss_test.py # run k-core-truss
			--k 5  # parameter k value
			--alpha 1  # parameter alpha value						
			--network example.dat  # network edges file

---

Dataset

• Amazon : https://snap.stanford.edu/data/com-Amazon.html
• Karate : https://networkrepository.com/soc-karate.php
• Polblogs : https://networkrepository.com/polblogs.php

other Dataset

we used in paper

---

Reference

[1] Stephen B Seidman. 1983. Network structure and minimum degree. Social networks 5, 3 (1983), 269–287.

[2] Fan Zhang, Long Yuan, Ying Zhang, Lu Qin, Xuemin Lin, and Alexander Zhou. 2018. Discovering strong communities with user engagement and tie strength. In International Conference on Database Systems for Advanced Applications. Springer, 425–441

[3] Francesco Bonchi, Arijit Khan, and Lorenzo Severini. 2019. Distance-generalized core decomposition. In Proceedings of the 2019 International Conference on Management of Data. 006–1023.

[4] Chen Zhang, Fan Zhang, Wenjie Zhang, Boge Liu, Ying Zhang, Lu Qin, and Xuemin Lin. 2020. Exploring finer granularity within the cores: Efficient (k, p)- core computation. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 181–192.

[5] Priya Govindan, Chenghong Wang, Chumeng Xu, Hongyu Duan, and Sucheta Soundarajan. 2017. The k-peak decomposition: Mapping the global structure of graphs. In Proceedings of the 26th International Conference on World Wide Web. 1441–1450.

[6] Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National security agency technical report 16, 3.1 (2008).

[7] Xudong Wu, Long Yuan, Xuemin Lin, Shiyu Yang, and Wenjie Zhang. 2019. Towards efficient k-tripeak decomposition on large graphs. In International Conference on Database Systems for Advanced Applications. Springer, 604–621.

[8] Balabhaskar Balasundaram, Sergiy Butenko, and Svyatoslav Trukhanov. 2005. Novel approaches for analyzing biological networks. Journal of Combinatorial Optimization 10, 1 (2005), 23–39.

[9] Shahram Shahinpour and Sergiy Butenko. 2013. Algorithms for the maximum k-club problem in graphs. Journal of Combinatorial Optimization 26, 3 (2013), 520554

[13]

[14] Tianhao Wang, Yong Zhang, Francis YL Chin, Hing-Fung Ting, Yung H Tsin, and Sheung-Hung Poon. 2015. A simple algorithm for finding all k-edge-connected components. Plos one 10, 9 (2015), e0136264.

[15] Friedhelm Victor, Cuneyt G Akcora, Yulia R Gel, and Murat Kantarcioglu. 2021. Alphacore: Data Depth based Core Decomposition. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 1625–1633.

[16] Zhenjun Li, Yunting Lu, Wei-Peng Zhang, Rong-Hua Li, Jun Guo, Xin Huang, and Rui Mao. 2018. Discovering hierarchical subgraphs of k-core-truss. Data Science and Engineering 32 (2018)136–149

---

Contact

Please contact ~~

---

Cite