Source-linked AI summary
Fuzzy communities and the concept of bridgeness in complex networks
Tamás Nepusz, Andrea Petróczi, László Négyessy, Fülöp Bazsó
TL;DR
The paper addresses community detection when vertices can participate in multiple communities and classical crisp partitions are inadequate. It models graded memberships through constrained similarity optimization, then derives bridgeness and supports automatic community-number selection. The method identifies fuzzy structure and community roles across benchmark and real-world networks, with 97.4% correct hard classifications in 1000 nonoverlapping test graphs and automatic community-number inference in all cases.
Problem
Classical community detection struggles with overlapping communities because it assigns each vertex to exactly one group.
Method
The method optimizes continuous membership degrees under constraints using similarity-based objectives, and can increase the community count using fuzzified modularity.
Results
97.4% of 1000 nonoverlapping test graphs had all vertices classified correctly after hardening, while the actual community number was inferred automatically in all cases.
Takeaways & Limitations
Bridgeness and centrality support identifying bridges, cores, and outliers in social, scientific collaboration, and cortical networks.
Abstract
from arXiv · showhide
We consider the problem of fuzzy community detection in networks, which complements and expands the concept of overlapping community structure. Our approach allows each vertex of the graph to belong to multiple communities at the same time, determined by exact numerical membership degrees, even in the presence of uncertainty in the data being analyzed. We created an algorithm for determining the optimal membership degrees with respect to a given goal function. Based on the membership degrees, we introduce a new measure that is able to identify outlier vertices that do not belong to any of the communities, bridge vertices that belong significantly to more than one single community, and regular vertices that fundamentally restrict their interactions within their own community, while also being able to quantify the centrality of a vertex with respect to its dominant community. The method can also be used for prediction in case of uncertainty in the dataset analyzed. The number of communities can be given in advance, or determined by the algorithm itself using a fuzzified variant of the modularity function. The technique is able to discover the fuzzy community structure of different real world networks including, but not limited to social networks, scientific collaboration networks and cortical networks with high confidence.
I. INTRODUCTION
Classical community detection struggles with networks whose vertices overlap communities or connect groups. The paper motivates measuring such sharedness while distinguishing bridges from outliers.
- Real-world networks often exhibit overlapping communities that classical methods assigning each vertex to exactly one community cannot capture.
- Bridge vertices connect structurally distinct groups, but their intuitive roles vary across social, protein, cortical, and word-association networks.
- In the example graph, vertex 5 appears to belong simultaneously to two densely connected communities rather than forming a meaningful singleton community.
- Hierarchical modularity optimization misleadingly merges vertex 5 with vertex 4 at the first step, obscuring its shared position.
- CPM classifies vertex 5 as an outlier, although removing it would disconnect the two densely connected subgroups because it is their sole connection.
A. Fuzzy community detection as a constrained optimization problem
The method represents each vertex’s memberships as continuous degrees summing to one and optimizes similarity-based objectives under constraints. It uses gradient-based optimization, with runtime scaling quadratically in the number of vertices.
- Fuzzy partitions: Fuzzy partitions allow each membership degree uik to vary continuously in [0, 1], while each vertex’s total membership degree remains 1.
- Similarity objective: The similarity framework treats connected vertices as similar and disconnected vertices as dissimilar, fitting membership assignments to prescribed pairwise similarities.
- Constrained optimization: The optimization finds a membership matrix U minimizing the nonlinear objective while satisfying membership constraints, using gradient-based iterative methods.
- Optimization procedure: Randomized initial memberships preserve result quality in simulations while improving convergence speed compared with uniform initialization, whose gradients can all vanish.
- Computational complexity: O(N^2ch) is the overall time complexity for N vertices, c communities, and h optimization steps, producing quadratic scaling when N ≫ c.
B. The concept of bridgeness
Bridgeness quantifies how evenly a vertex’s membership is distributed across communities. Combined with centrality, it helps distinguish community cores, bridges, and potential outliers.
- Bridgeness measures a vertex’s sharedness across communities using its membership vector’s normalized distance from a reference vector.
- A vertex belonging to one community has zero bridgeness, whereas equal membership across all communities yields bridgeness of 1.
- Maximum bridgeness can also indicate an outlier, so centrality is needed to distinguish genuine bridges from vertices weakly belonging to communities.
- Plotting centrality against bridgeness provides a visual aid for selecting bridge vertices and outliers.
- High centrality with bridgeness near zero suggests a community core, while high centrality with bridgeness near one suggests a bridge-like position.
III. PARAMETRIZATION OF THE ALGORITHM
The algorithm has several parameters, most of which have reasonable default values; selecting the number of clusters c is the main exception.
- Most algorithm parameters can generally use reasonable default values.
- The number of clusters c requires a separate process to identify its most suitable value.
A. Choosing the number of communities
The method determines the number of fuzzy communities by progressively increasing c during optimization and selecting the value with the highest fuzzified modularity.
- c is the method’s key parameter because it determines how many communities the algorithm tries to discover.
- Spectral approaches often require subjective threshold choices when using eigenvalues to determine c.
- The algorithm starts with a fuzzy bisection at c = 2, then increases c when optimization reaches a local minimum.
- Fuzzified modularity replaces crisp same-community membership with a fuzzy similarity based on the dot product of membership vectors.
- The selected number of communities is the c producing the highest fuzzified modularity Qf.
B. Parametrization of similarity and dissimilarity constraints
Similarity targets and weights determine which vertex relationships the algorithm fits, allowing domain knowledge and uncertainty about missing edges to be incorporated.
- With no additional prior knowledge, desired similarity equals 1 for adjacent vertices and 0 for nonadjacent vertices, while all weights equal 1.Matching both connected and disconnected pairs prevents the solution in which every vertex belongs to one community.
- Weights can emphasize relationships whose calculated similarity should match an expected value and omit relationships whose expected similarity is uncertain.
- In friendship networks, direct neighbors may be treated as similar while second-order neighbors are treated as dissimilar.This distance-based assumption reflects that second-order pairs were likely to meet through common acquaintances.
- Setting weights of experimentally untested connections to zero distinguishes them from connections experimentally found to be nonexistent.The involved vertices’ similarity can then be checked after analysis.
- Distance-based relaxation assigns no similarity specification to vertices farther than k steps away by setting their weights to zero.For k = 2, direct neighbors are similar, nonneighboring vertices within two steps are dissimilar, and farther vertices are unspecified.
- Other normalized similarity measures, including cosine and Jaccard similarity, can also be used.
IV. BENCHMARKS AND APPLICATIONS
The method is intended to quantify overlapping community structure and is parameterized to identify bridge vertices from their bridgeness scores.
- The algorithm is designed to discover overlapping communities and quantify vertices’ membership degrees.
- A vertex is automatically classified as a bridge when its bridgeness is at least one standard deviation above the network’s mean.
A. Benchmarks on computer-generated graphs
On generated graphs, the algorithm recovered known nonoverlapping communities and identified bridge-like vertices in overlapping structures. Its inferred community assignments and bridgeness scores were evaluated against controlled benchmarks.
- 97.4% of 1000 nonoverlapping graphs had all vertices classified correctly after fuzzy partitions were converted using dominant communities.The algorithm also inferred the actual number of communities automatically in every test case using fuzzified modularity.
- The algorithm inferred the actual number of communities automatically in all nonoverlapping benchmark cases using fuzzified modularity.
- Benchmark graphs varied inter-community links kout from 0 to 24 while keeping the average degree kin + kout constant.At kout = 24, the graph practically became an Erdős-Rényi random graph without community structure.
- In overlapping graphs, bridge candidates were designed with connection patterns differing from regular vertices, although randomization meant not every candidate became a bridge.
- Bridge and regular vertices showed different bridgeness distributions, with a Kolmogorov-Smirnov test yielding p-value less than 2.2×10^-16.Regular vertices usually had lower bridgeness scores, and 92.8% of identified bridges were bridge candidates.
B. Social and collaboration networks
The method was applied to a UK university faculty network and a scientific co-authorship network. It recovered school-aligned communities, characterized bridge and core vertices, and selected a community count for the collaboration network.
- In the UK faculty network, 75 of 81 vertices were classified correctly after defuzzification by dominant communities.Four misclassified vertices all had bridgeness greater than 0.7, while two lacked an expected school assignment because of missing questionnaire information.
- The faculty network’s maximal fuzzy modularity was Qf = 0.2826 at c = 6, versus Qf = 0.2541 at c = 3, without a significant improvement.
- For c = 3, highly degree-corrected bridgeness scores marked individuals participating in all three communities, whereas low scores marked community cores.Degree correction suppressed high apparent bridgeness among low-degree community peripheries.
- Uncorrected bridgeness can measure centrality within a vertex’s dominant community by subtracting the score from 1.
- In the co-authorship network’s giant component, fuzzified modularity selected c = 30 communities with optimum Qf = 0.7082.The community count was confirmed by visual inspection of Laplacian eigenvalues; 31 standardized high-bridgeness vertices were mostly post-doctorate researchers collaborating with multiple senior researchers.
C. Cortical networks and the case of incomplete data
The cortical dataset contains uncertain directed connections between visual and somatosensory areas, and the method models this uncertainty while detecting biologically meaningful fuzzy subdivisions and bridges.
- The macaque cortical graph has 45 brain-area vertices, 463 directed connections, and 13 suspected connections, including 11 heteromodal links.
- The method assigned zero weight to suspected or nonreciprocal connections and reached optimal fuzzy modularity 0.2766 at c = 4.
- At c = 4, fuzzy detection separated dorsal and ventral visual streams, with only areas 7a and V IP misclassified while retaining bridgelike properties.
- The detected bridges corresponded to areas associated with integrating visual, tactile, proprioceptive, and higher-level sensory signals.
- Pairwise vertex similarity was used to approximate probabilities for suspected connections through membership-based estimates of shared community affiliation.
- The analysis found all supposed connections of area LIP less likely than those of V IP, with V IP connections to areas 4 and 6 most probable.
D. Comparison with other overlapping community detection algorithms
The proposed method was compared with CPM, a spectral approach, and a prior fuzzy method on synthetic and cortical networks. It matched expected structure on the example graph and provided complementary evidence on the harder cortical graph.
- All evaluated algorithms detected the proper community structure of the example graph, although the spectral method required a three-clique variant for meaningful correlation calculations.
- On the example graph, the proposed and Zhang methods assigned vertex 5 membership degree 0.5 in both communities, while CPM labeled it an outlier.
- For the cortical graph, CPM failed to reveal the dorsal–ventral visual subdivision, while the Zhang method classified 40% of vertices as bridges at m = 2.
- The proposed method’s bridge findings did not contradict existing methods: every bridge it identified was classified as a bridge by at least one other method.
- Capocci’s method complements the proposed approach by finding local communities around vertices, whereas the proposed method describes global structure and indicates bridges.
V. CONCLUSION
The paper extends community detection with graded, multiple community memberships and introduces bridgeness to quantify how vertices are shared across communities. The algorithm is useful for relatively small networks and identifies important bridge vertices across several network types.
- The fuzzy extension assigns every vertex graded memberships in at least one community, allowing simultaneous membership in multiple communities.
- The method optimizes membership similarities so connected vertices become similar and disconnected vertices dissimilar.Membership values are organized in a matrix and optimized with gradient-based constrained methods.
- Bridgeness measures how strongly a vertex is shared between communities and highlights important vertices in social, scientific collaboration, and cortical networks.A transformed bridgeness measure also quantifies centrality relative to a vertex’s dominant communities.
- The algorithm is expected to be most useful for relatively small datasets, up to approximately a thousand vertices.