Source-linked AI summary
ABACUS: frequent pAttern mining-BAsed Community discovery in mUltidimensional networkS
Michele Berlingerio, Fabio Pinelli, Francesco Calabrese
TL;DR
Because conventional community discovery has largely focused on single-dimension ties, the paper defines multidimensional communities through shared monodimensional community memberships. ABACUS mines those memberships as frequent closed itemsets, and the authors report applying it to real networks and comparing it with prior approaches.
Problem
Community discovery has largely focused on single-dimension connections, although real networks can contain multiple relationship types or values whose distinctions matter.
Source: §1 · p. 2Method
ABACUS finds frequent closed itemsets over nodes’ monodimensional community memberships to extract multidimensional communities.
Source: §4.2 · p. 10, §4.3 · p. 13Results
The authors report applying ABACUS to real multidimensional networks and comparing it with prior community-discovery approaches.
Source: §1 · p. 4Takeaways & Limitations
The lattice of mined itemsets lets users navigate multidimensional communities of different sizes in a way previous methods did not permit.
Source: §6 · p. 25The reported results use one selected combination of monodimensional community discovery and frequent closed-itemset mining, and changing the community algorithm may yield very different communities.
Source: §5.1 · p. 14
Abstract
from arXiv · showhide
Community Discovery in complex networks is the problem of detecting, for each node of the network, its membership to one of more groups of nodes, the communities, that are densely connected, or highly interactive, or, more in general, similar, according to a similarity function. So far, the problem has been widely studied in monodimensional networks, i.e. networks where only one connection between two entities can exist. However, real networks are often multidimensional, i.e., multiple connections between any two nodes can exist, either reflecting different kinds of relationships, or representing different values of the same type of tie. In this context, the problem of Community Discovery has to be redefined, taking into account multidimensional structure of the graph. We define a new concept of community that groups together nodes sharing memberships to the same monodimensional communities in the different single dimensions. As we show, such communities are meaningful and able to group highly correlated nodes, even if they might not be connected in any of the monodimensional networks. We devise ABACUS (Apriori-BAsed Community discoverer in mUltidimensional networkS), an algorithm that is able to extract multidimensional communities based on the apriori itemset miner applied to monodimensional community memberships. Experiments on two different real multidimensional networks confirm the meaningfulness of the introduced concepts, and open the way for a new class of algorithms for community discovery that do not rely on the dense connections among nodes.
1 Introduction
The paper argues that single-dimension views can miss the semantic differences among relationships in real networks. It defines communities through shared memberships across dimensions and introduces ABACUS to extract them by mining those memberships.
1 Introduction
- Single-connection or collapsed-network views can lose semantic distinctions among actors’ relationships, limiting the information available to community discovery.The paper notes that real ties may reflect different relationship types or different values of one relationship.Source: §1 · p. 2
- Multidimensional communities group nodes that share memberships in the same monodimensional communities across dimensions, and can include nodes unconnected in every dimension.The associated dimension subset gives each community a semantic description.Source: §1 · p. 3
- ABACUS extracts multidimensional communities by finding frequent closed itemsets over nodes’ dimension–community memberships.It first extracts monodimensional communities separately, then represents each node’s memberships as items.Source: §1 · pp. 3–4
- The paper introduces multidimensional communities and ABACUS, and reports applying the algorithm to real networks and comparing it with earlier approaches.The introduction presents the concept and algorithm as its contributions, alongside real-network application and comparison.Source: §1 · p. 4
2 Related work
Earlier community-discovery work largely treated networks as monodimensional, using connectivity, graph statistics, or related structures. The paper distinguishes its multidimensional community formulation from prior approaches and identifies two related methods as comparison baselines.
2 Related work
- Many established approaches detect communities in monodimensional networks, using link density, graph statistics, label propagation, cliques, or random walks.The section also notes approaches based on modularity and information theory.Source: §2 · pp. 4–5
- Among multidimensional approaches, extends modularity, uses inferred dimensions for node classification, and characterizes communities through interplay among dimensions.The paper’s method instead uses frequent itemset mining to extract communities described by their dimension subsets.Source: §2 · pp. 5–6
- Other related work addresses heterogeneous networks, query-based relation importance, or frequent pattern mining in multi-relational data, rather than this community-discovery formulation.Cross-graph quasi-cliques and constrained cliques also differ because this paper’s community concept is independent of node-link density.Source: §2 · p. 6
- The authors select and as the approaches most related to their problem formulation and use them as comparison baselines.Source: §2 · p. 6
3 Multidimensional networks
The paper models multidimensional networks as edge-labeled multigraphs and illustrates their range with real-world examples. Its DBLP and Query Log datasets represent contrasting network types, dimension counts, and scales.
3 Multidimensional networks
- Multidimensional networks can represent transportation modes, online social services, or co-authorship venues as distinct dimensions.Source: §3 · p. 7
3.1 A model for multidimensional networks
- The model uses an undirected edge-labeled multigraph G = (V, E, L), with dimensions as labels and at most one edge per node pair and label.A node appears in a dimension when at least one adjacent edge carries that label; node labels are not considered.Source: §3.1 · p. 7
3.2 Real world dataset
- DBLP represents co-authorship by conference: its 558,800 nodes and 2,668,497 edges span 2,536 dimensions, with edge weights counting joint papers per conference.The dimensions are conferences held in 2000–2010; conference editions are grouped together.Source: §3.2 · pp. 7–8
- Query Log represents co-occurring query words by clicked-result rank bins, producing 131,268 nodes and 2,313,224 edges across five dimensions.The network was built from about 20 million queries submitted by 650,000 users; edge weights count queries in which word pairs co-occurred within a dimension.Source: §3.2 · p. 8
- The selected datasets contrast a social network with thousands of categorical dimensions and an information network with five numerical dimensions, partially covering several network classes.Source: §3.2 · p. 9
4 The ABACUS framework
The ABACUS framework defines multidimensional communities through shared monodimensional community memberships, then maps those memberships to frequent closed itemsets for extraction.
4.1 A new concept
- Nodes sharing memberships to the same monodimensional communities can form a multidimensional community even when they are not directly connected in any dimension.The authors note that monodimensional algorithms and edge weights do not fully convey this cross-dimension information.Source: §4.1 · p. 10
4.2 From communities to itemsets
- After detecting communities separately in each dimension, ABACUS treats nodes as transactions and dimension-community memberships as items, then extracts frequent closed itemsets.Support counts the nodes sharing a multidimensional community; size counts the dimensions it involves.Source: §4.2 · pp. 10–11
- In the example, nodes 3 and 5 form a community despite being unconnected in every dimension because they share four community memberships.With minimum support σ = 2, closed frequent itemsets summarize the frequent itemsets without returning redundant non-closed ones.Source: §4.2 · p. 12
4.3 The ABACUS algorithm.
- ABACUS takes a network, a monodimensional community detector, and a minimum-support threshold; it splits dimensions, records node memberships, and mines the resulting transactions.Overlapping detectors can yield more membership combinations and communities, but do not change the type of community ABACUS finds.Source: §4.3 · p. 13
- ABACUS's added mapping cost is a linear scan; total complexity inherits the chosen itemset miner and community detector, and the evaluation uses a weight-aware detector.The experiments use a non-overlapping community detector for simplicity, without changing the definition of the communities sought.Source: §4.3 · p. 13
5 Case study on DBLP and Query Log
The case study applies ABACUS to DBLP and Query Log, uses MCD, support, and itemset size to inspect results, and compares ABACUS with MD and GL across community counts, overlap, examples, and runtime.
5.1 Tools
- Experiments use weighted label propagation for monodimensional communities, minimum support 2, and Eclat for frequent closed itemset mining; changing the community-discovery algorithm may yield very different communities.The authors report results only for the selected choices, while the ability to find potentially unconnected communities comes from the problem mapping.Source: §5.1 · pp. 14–15
5.2 Experiments
- MCD, support, and itemset size distributions can guide post-filtering, while constraints can target dimensions or their properties; the authors leave application-driven constraints for future work.MCD showed no clear direct correlation with closeness, PageRank, degree, or betweenness centrality.Source: §5.2 · pp. 16–17
5.3 Comparison with previous approaches
- The comparison uses MD, which collapses the network before community discovery, and GL, which couples node representations across dimensions using ω.The study compares incrementally sized DBLP year-window networks because the baselines differ in scalability and memory use.Source: §5.3 · pp. 19–20
5.3.1 Quantitative evaluation
- As year subsets grow, MD’s community count becomes nearly stable after four years, while ABACUS’s grows until the final two or three steps; ABACUS-only communities include disconnected nodes.In the small-net comparison, GL with ω = 0 returns more communities than other tested ω values because it treats dimensions separately.Source: §5.3.1 · pp. 21, 23, Figure 10 · p. 21
5.3.2 Qualitative evaluation
- The methods return distinct community types: ABACUS can find unconnected nodes sharing memberships across dimensions, while baseline-only examples arise from nodes connected in different dimensions.The comparison counts identical communities after removing ABACUS’s dimension information.Source: §5.3.1 · p. 22, §5.3.2 · pp. 23–24, Figure 13 · p. 24
5.3.3 Scalability
- On large nets, ABACUS took 32–1200 seconds versus MD’s 380–13,500 seconds; on small nets, ABACUS took under one to 2.5 seconds, versus up to 7.5 seconds for MD and 86 seconds for GL.GL could not process large nets because its memory use exceeded 4GB.Source: §5.3.3 · p. 25
6 Conclusions and future work
The conclusion defines multidimensional communities through shared memberships in monodimensional communities and combines community discovery with frequent itemset mining. Its closed-itemset lattice supports exploring communities across pattern lengths, while applications remain future work.
6 Conclusions and future work
- ABACUS combines a monodimensional community discovery algorithm, which may allow overlapping communities, with frequent itemset mining to form multidimensional communities.The itemsets merge discovered monodimensional communities.Source: §6 · p. 25
- Browsing the closed-itemset lattice exposes multidimensional communities of different sizes and supports navigating network structure in ways previous methods could not.Pattern length determines community size.Source: §6 · p. 25
- Fig. 14 compares ABACUS with MD on the large network and with all baselines on the small networks using running times.The caption provides the comparison scope but no outcome values.Source: Figure 14 · p. 25
- The authors propose potential applications in studying dimension interplay, including mobility and communication, user-mobility similarity, and infectious-disease spread,,.Analysis of these applications is left for future research.Source: §6 · p. 26