aminography

Graph Research Project

CBLSE

CBLSE (Clique Based Local Seed Expansion) is a novel approach to detect communities in graph. (Available on gitlab)

The implementation contains 9 seed expansion methods:

  • Local Improvement Seed Expansion
  • Local Diffusion Ordered Seed Expansion
  • Biased Search Seed Expansion
  • Similarity Ordered Seed Expansion
  • Seed Similarity Seed Expansion
  • Community Similarity Seed Expansion
  • Personalized PageRank Seed Expansion
  • Neighbourhood Inflated Personalized PageRank Seed Expansion
  • Heat Kernel Seed Expansion

Customized data structures comparison:

  • HashSet takes memory about 64 bytes per element [64,388,704 bytes | 2244 ms for 1,000,000 elements]
  • LinkedHashSet takes memory about 72 bytes per element [72,388,712 bytes | 623 ms for 1,000,000 elements]
  • FastHashSet takes memory about 56 bytes per element [56,388,680 bytes | 79 ms for 1,000,000 elements (549 ms for non-IUniqueIdHashable)]
  • FastLinkedHashSet takes memory about 64 bytes per element [64,388,688 bytes | 82 ms for 1,000,000 elements (549 ms for non-IUniqueIdHashable)]
  • HashMap takes memory about 80 bytes per element [80,388,672 bytes | 2092 ms for 1,000,000 elements]
  • LinkedHashMap takes memory about 88 bytes per element [88,388,680 bytes | 314 ms for 1,000,000 elements]
  • FastHashMap takes memory about 80 bytes per element [80,388,672 bytes | 463 ms for 1,000,000 elements]
  • FastLinkedHashMap takes memory about 88 bytes per element [88,388,680 bytes | 414 ms for 1,000,000 elements]
  • FastSparseVector takes memory about 64 bytes per element [64,388,672 bytes | 295 ms for 1,000,000 elements]
  • FastLinkedSparseVector takes memory about 72 bytes per element [72,388,680 bytes | 206 ms for 1,000,000 elements]
Clique Based Local Seed Expansion