Evaluating Overlapping Communities with the Conductance of their Boundary Nodes

Abstract

Usually the boundary of a community in a network is drawn between nodes and thus crosses its outgoing links. If we construct overlapping communities by applying the link-clustering approach nodes and links interchange their roles. Therefore, boundaries must drawn through the nodes shared by two or more communities. For the purpose of community evaluation we define a conductance of boundary nodes of overlapping communities analogously to the graph conductance of boundary-crossing links used to partition a graph into disjoint communities. We show that conductance of boundary nodes (or normalised node cut) can be deduced from ordinary graph conductance of disjoint clusters in the network's weighted line graph introduced by Evans and Lambiotte (2009) to get overlapping communities of nodes in the original network. We test whether our definition can be used to construct meaningful overlapping communities with a local greedy algorithm of link clustering. In this note we present encouraging results we obtained for Zachary's karate-club network.

9 pages, 7 figures, corrected version, two sections and some sentences deleted, footnote 7 (p. 7) added

References in corpus (5)

• Cooperative Game Theory Approaches for Network Partitioning
• Line Graphs, Link Partitions and Overlapping Communities
• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• Identifying Overlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers: A Comparison of Three Approaches
• Identification of Overlapping Communities by Locally Calculating Community-Changing Resolution Levels

Cited by in corpus (2)

• Detecting Overlapping Link Communities by Finding Local Minima of a Cost Function with a Memetic Algorithm. Part 1: Problem and Method
• Estimating Thematic Similarity of Scholarly Papers with Their Resistance Distance in an Electric Network Model