Limits and Algorithms in Network Science
Limits of Modularity and Optimized Greedy Algorithms
Network Science
section 9.4.3 and Asymptotic resolution bounds of generalized modularity
and multi-scale community detection
Stephen Trempel
Community Detection
●
Create partitions that best represent the community structure
●
Unknown number of partitions
●
No mathematical definition
[1]
Modularity
●
Measures a set of partitions
●
Higher modularity implies better set of partitions
[1]
Modularity
●
L
c
: Number of links
●
k
c
: Sum of degrees
●
Range: [-½ to 1]
●
Brute force infeasible
[1,2]
Greedy Algorithm
1.
Initialize with N communities
2.
Until # communities == 1
3.
Combine clusters for maximum
modularity
4.
Store best so far
5.
Return best
●
Efficient: O[(L + N)N]
●
Resolution Limit!
○
Large communities split
○
Small communities merged
[1]
Resolution Parameter
●
Big 𝛾 → small communities
●
Small 𝛾 → big communities
●
W
rs
: Inter community density
●
W
tt
: Density of t
Big 𝛾
Small 𝛾
[3]
Plateau Problem
We want this →
But what if →
[3]
Plateau Problem
Min W
tt
Max W
rs
[3]
Plateau Problem
Min W
tt
Max W
rs
[3]
Multi-scale Community Detection Algorithm
[3]
1.
Initialize with N communities
2.
Run greedy with small 𝛾
3.
Repeat with larger 𝛾 for each
community
4.
Stop when a “good”
community is found
When to stop?
Multi-scale Community Detection Algorithm
Min W
tt
Max W
rs
[3]
Multi-scale Community Detection Algorithm
[3]
𝛾
Multi-scale Community Detection Algorithm
[3]
𝛾
Multi-scale Community Detection Algorithm
[3]
𝛾
Multi-scale Community Detection Algorithm
[3]
Questions?
Sources
[1] Barabási, A. (2015), Network Science, Cambridge University Press
[2] Wikipedia. Modularity (networks).
https://en.wikipedia.org/wiki/Modularity_(networks)
[3] Xiaoyan Lu, Brendan Cross, Boleslaw K. Szymanski. Asymptotic resolution bounds of
generalized modularity and multi-scale community detection.
https://arxiv.org/pdf/1902.04243.pdf
This section delves into the complexities of modularity and optimized greedy algorithms for community detection in network science. It covers topics such as asymptotic resolution bounds, modularity measures, the greedy algorithm process, the resolution parameter, plateau problems, and multi-scale community detection algorithms. Through a series of visual explanations, the content explores the challenges and solutions in creating optimal partitions that best represent community structures.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Limits of Modularity and Optimized Greedy Algorithms Network Science section 9.4.3 and Asymptotic resolution bounds of generalized modularity and multi-scale community detection Stephen Trempel
Community Detection Create partitions that best represent the community structure Unknown number of partitions No mathematical definition [1]
Modularity Measures a set of partitions Higher modularity implies better set of partitions [1]
Modularity Lc: Number of links kc: Sum of degrees Range: [- to 1] Brute force infeasible [1,2]
Greedy Algorithm 1. Initialize with N communities 2. Until # communities == 1 3. Combine clusters for maximum modularity 4. Store best so far 5. Return best Efficient: O[(L + N)N] Resolution Limit! Large communities split Small communities merged [1]
Resolution Parameter Big ? ? Big ? small communities Small ? big communities Small ? Wrs: Inter community density Wtt: Density of t [3]
Plateau Problem We want this But what if [3]
Plateau Problem Min Wtt Max Wrs [3]
Plateau Problem Max Wrs Min Wtt [3]
Multi-scale Community Detection Algorithm 1. Initialize with N communities 2. Run greedy with small ? 3. Repeat with larger ? for each community 4. Stop when a good community is found When to stop? [3]
Multi-scale Community Detection Algorithm Max Wrs Min Wtt [3]
Sources [1] Barab si, A. (2015), Network Science, Cambridge University Press [2] Wikipedia. Modularity (networks). https://en.wikipedia.org/wiki/Modularity_(networks) [3] Xiaoyan Lu, Brendan Cross, Boleslaw K. Szymanski. Asymptotic resolution bounds of generalized modularity and multi-scale community detection. https://arxiv.org/pdf/1902.04243.pdf
