1 of 41

 

Deming Chu, Fan Zhang, Xuemin Lin, Wenjie Zhang, Ying Zhang, Yinglong Xia, Chengyi Zhang

IEEE International Conference on Data Engineering 2020

1

2 of 41

Motivation

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

2

 

 

Community Scoring Metric

can evaluate subgraph quality

 

2

3 of 41

Applications at a Glance

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

3

3

4 of 41

Two Problems

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

4

 

4

5 of 41

Roadmap

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

5

5

6 of 41

 

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

6

 

 

6

7 of 41

Definition: Coreness

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

7

⬤ Nodes with coreness 3

⬤ Nodes with coreness 2

⬤ Nodes with coreness 1

7

8 of 41

Definition: Community Scoring Metric

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

8

 

 

Most metrics are based on Primary Values, we pick 6 typical ones

​

8

9 of 41

Problem Definition

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

9

3-core set

2-core set

1-core set

 

 

 

 

9

10 of 41

Roadmap

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

10

10

11 of 41

 

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

11

3-core set

Score=0.99

2-core set

Score=0.88

1-core set

Score=0.77

 

11

12 of 41

 

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

12

 

 

 

 

 

12

13 of 41

Baseline Solution (Analysis)

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

13

 

13

14 of 41

Roadmap

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

14

14

15 of 41

Intuition of Improved Algorithms

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

15

 

 

15

16 of 41

Intuition of Improved Algorithms

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

16

 

16

17 of 41

Intuition of Improved Algorithms

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

17

 

 

 

17

18 of 41

Intuition of Improved Algorithms

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

18

 

 

 

18

19 of 41

Intuition of Improved Algorithms

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

19

 

 

 

19

20 of 41

Intuition of Improved Algorithms

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

20

 

 

 

 

 

20

21 of 41

Intuition of Improved Algorithms

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

21

 

21

22 of 41

Intuition of Improved Algorithms

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

22

 

22

23 of 41

Vertex Ordering

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

23

23

24 of 41

Neighbor Query

  • Neighbor Query:

​

​

​

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

24

 

  1. Vertex Ordering & Build Position Tags
  2. Answer Neighbor Query according to the table & tags

Time: return neighbor query in Optimal time

Position Tags

Neighbor Query

24

25 of 41

 

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

25

 

 

25

26 of 41

 

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

26

 

26

27 of 41

Roadmap

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

27

27

28 of 41

Core Forest

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

28

2-core

tree node

[1] Matula, David W., and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. JACM 1983.

 

28

29 of 41

 

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

29

 

 

29

30 of 41

Roadmap

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

30

30

31 of 41

Dataset Statistics

  • 10 Public Networks from SNAP & NetworkRepository
  • With up to 65M nodes & 2B edges

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

31

31

32 of 41

Experimental Setting

  • A Quad-Core Linux server with 128G memory

​

  • Algorithm
    • Baseline (Baseline) & Improved Algorithms (Optimal)
    • Six Community Scoring Metrics

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

32

32

33 of 41

Runtime (Ignoring Strategy)

CC: Clustering Coefficient

  • Too many runtime figures, ignore some in the slide
  • Ignore-1: 6 metrics -> 2 categories
  • Ignore-2: 2 problems -> 1 column��

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

33

Baseline Score Computation

Optimal Score Computation

Other than CC

 

 

CC

33

34 of 41

Runtime (Score Computation)

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

34

Baseline Score Computation

Optimal Score Computation

CC

Other Than CC

34

35 of 41

Runtime (Include Indexing)

  • Score Computation + Indexing: Optimal still outperforms 1-2 orders of magnitude

​

  • Index Sharing: Optimal can efficiently compute multiple metrics and their combination

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

35

CC

Other Than CC

35

36 of 41

Application: Densest Subgraph

36

[1] Fang, Yixiang, et al. Efficient algorithms for densest subgraph discovery. PVLDB 2019.

 

 

Better is bold

runtime

average degree

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

36

37 of 41

Application: Maximum Clique

  •  

37

 

 

 

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

37

38 of 41

 

  •  

38

 

 

 

 

 

 

........

 

 

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

38

39 of 41

Roadmap

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

39

39

40 of 41

Conclusion

  •  

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

40

40

41 of 41

Q & A

Finding the Best k in Core Decomposition: A Time and Space Optimal Solution

41

41