matlab - How to find bridges (community connecting nodes) in large networks represented using the adjacency matrix -

i have networks of 10k 100k nodes connected. these nodes typically grouped clusters of communities connected many edges between them , there hubs etc. between communities there nodes few edges bridging / connecting communities together. these datasets in adjacency matrices

i have tried spectral clustering (ding et al 2001) slow on large data sets , seems stop working when there lot of ambiguity (bridges not bridge route cluster- other communities can act alternative proxy routes).

i have tried of methods martelot such newman algorithm modularity optimisation have not incorporated stability optimisation functions in effort (could crucial?). on synthetic data sets clusters created random graphs (er graphs) methods work on real ones there nested hierarchy results scattered. using standalone visualization application/tool bridges evident though.

what methods recommend/advise try? using matlab.

what want do, exactly? detect communities, or bridges between them? 2 different problems. once have communities, it's straightforward enough identifying edges connecting nodes 2 distinct communities. so, guess want detect communities.

there thousands methods purpose, of them implemented in matlab, such 1 cite, or generalized louvain algorithm (also based on modularity optimization). however, of them rather available c or c++ programs, such infomap (based on data compression paradigm), walktrap (clustering using random walk-based distance), markov cluster (simulates propagation mechanism), , list goes on...

those tools formalize notion of community structure more or less differently, potentially leading different (estimated) community structures, when applied on same network. , of course, different communities means different bridges, too. question rather know how pick appropriate method data. seem have a priori knowledge regarding networks studying, should use make choice (rather programming language). instance, if don't state explicitly, seem looking hierarchical community structure: not tools able detect kind of structure. similarly, if think 1 node can belong several communities @ same time, should consider looking overlapping communities, instance using cfinder (based on clique percolation).

i'd advise have @ excellent review of community detection, might find interesting information allowing pick method: community detection in graphs. also, programming point of view, i'd advise play igraph library (available c, r , python): contains several standard community detection tools. can try them on data , see get.