Fast algorithms for determining (generalized) core groups in social networks

DOI10.1007/s11634-010-0079-yzbMath1284.05252OpenAlexW2147991930MaRDI QIDQ2442801

Vladimir Batagelj, Matjaž Zaveršnik

Publication date: 1 April 2014

Published in: Advances in Data Analysis and Classification. ADAC (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11634-010-0079-y

zbMATH Keywords

decompositiongraph algorithmcorelarge network

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Partitions of sets (05A18) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (32)

A parameterized complexity view on collapsing \(k\)-cores ⋮ Parallel Maximum Clique Algorithms with Applications to Network Analysis ⋮ On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ An order approach for the core maintenance problem on edge-weighted graphs ⋮ Random networks are heterogeneous exhibiting a multi-scaling law ⋮ Restricted bi-pattern mining ⋮ A family of pairwise multi-marginal optimal transports that define a generalized metric ⋮ Efficient algorithms for finding diversified top-\(k\) structural hole spanners in social networks ⋮ OCSM: finding overlapping cohesive subgraphs with minimum degree ⋮ Discovering subjectively interesting multigraph patterns ⋮ Bounds and algorithms for graph trusses ⋮ Efficient and effective community search ⋮ Parsimonious formulations for low-diameter clusters ⋮ Ak-shell decomposition method for weighted networks ⋮ Practical Minimum Cut Algorithms ⋮ Core Decomposition, Maintenance and Applications ⋮ The maximum clique interdiction problem ⋮ Percolation on complex networks: theory and application ⋮ Metanetworks of artificially evolved regulatory networks ⋮ An efficient exact algorithm for triangle listing in large graphs ⋮ Incremental problems in the parameterized complexity setting ⋮ A parallel maximum clique algorithm for large and massive sparse graphs ⋮ Identifying and ranking influential spreaders in complex networks by neighborhood coreness ⋮ Degree sequences of monocore graphs ⋮ The k-Dense Method to Extract Communities from Complex Networks ⋮ Density decompositions of networks ⋮ Space efficient linear time algorithms for BFS, DFS and applications ⋮ Network analysis of Zentralblatt MATH data ⋮ Experiments on \(F\)-restricted bi-pattern mining ⋮ Tree decompositions and social graphs ⋮ Distributed Core Decomposition in Probabilistic Graphs ⋮ Graph Kernels: A Survey

Uses Software

• Pajek
• Pajek datasets
• LaNet-vi

Cites Work

• Unnamed Item
• Unnamed Item
• \(k\)-core architecture and \(k\)-core percolation on complex networks
• Asymptotic normality of the \(k\)-core in random graphs
• \(k\)-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases
• An upper bound for the chromatic number of a graph and its application to timetabling problems

This page was built for publication: Fast algorithms for determining (generalized) core groups in social networks