PaperlayerView exact revision on arXiv

Source-linked AI summary

Combining complex networks and data mining: why and how

M. Zanin, D. Papo, P. A. Sousa, E. Menasalvas, A. Nicchi, E. Kubik, S. Boccaletti

arXiv:1604.08816v2physics.soc-phcs.DBcs.IRcs.SIphysics.data-an

TL;DR

The paper examines how data mining and complex network theory can jointly represent and analyze complex systems. It reviews synergistic applications and argues that each field supplies tools addressing limitations of the other, while noting methodological choices affect results.

  • Problem

    Data mining and complex network theory share representational goals but remain insufficiently integrated, despite offering different views of complex systems.

  • Method

    The paper reviews both fields, illustrates their concepts, and surveys contexts where network metrics and data-mining methods are used together.

  • Results

    The review shows that data mining can improve network representations and discrimination, while network representations provide data scientists with quantitative system variables.

  • Takeaways & Limitations

    Combining the fields can support node and connection selection, group discrimination, diagnostic or prognostic applications, and more structured information representation.

  • Takeaways & Limitations

    Classification algorithms and validation strategies can materially affect results, so their selection should be treated as a fundamental methodological step.

Abstract

from arXiv · show

The increasing power of computer technology does not dispense with the need to extract meaningful in- formation out of data sets of ever growing size, and indeed typically exacerbates the complexity of this task. To tackle this general problem, two methods have emerged, at chronologically different times, that are now commonly used in the scientific community: data mining and complex network theory. Not only do complex network analysis and data mining share the same general goal, that of extracting information from complex systems to ultimately create a new compact quantifiable representation, but they also often address similar problems too. In the face of that, a surprisingly low number of researchers turn out to resort to both methodologies. One may then be tempted to conclude that these two fields are either largely redundant or totally antithetic. The starting point of this review is that this state of affairs should be put down to contingent rather than conceptual differences, and that these two fields can in fact advantageously be used in a synergistic manner. An overview of both fields is first provided, some fundamental concepts of which are illustrated. A variety of contexts in which complex network theory and data mining have been used in a synergistic manner are then presented. Contexts in which the appropriate integration of complex network metrics can lead to improved classification rates with respect to classical data mining algorithms and, conversely, contexts in which data mining can be used to tackle important issues in complex network theory applications are illustrated. Finally, ways to achieve a tighter integration between complex networks and data mining, and open lines of research are discussed.

1. Introduction

Growing data volumes make extracting compact, meaningful representations increasingly necessary. This review argues that data mining and complex network theory share goals and can be combined synergistically.

  • Motivation: Data mining emerged to uncover hidden patterns in large datasets and transform them into understandable structures.
  • Motivation: Complex network theory represents relationships in systems ranging from power grids to social interactions and brains.
  • Shared goals: Data mining and complex network analysis both extract information from complex systems to create representations useful for subsequent analysis.
  • Synergy: Their combination can add value because data mining and network theory provide different approaches despite overlapping goals and procedures.
  • Review scope: The review connects two communities by introducing both fields and examining network-enhanced classification and data-mining-based functional-network reconstruction.
  • Network representation: Complex networks remove unnecessary system details, represent constituent parts and interactions, and quantify the resulting topology with network metrics.

Structural vs. functional networks

Structural networks encode explicit physical links, whereas functional networks infer relationships from coordinated dynamics. Functional-network reconstruction depends on interconnected choices of connectivity metric, threshold, and topological measures.

  • Network types: Structural networks map explicit interactions directly, while functional networks quantify relationships inferred from the dynamics of system elements.
  • Network types: Brain analysis illustrates the distinction between physical fibre connections and functional information transfer during tasks.
  • Reconstruction choices: Functional-network reconstruction requires selecting a connectivity metric, a threshold for retaining statistically significant links, and topological metrics.
  • Reconstruction choices: These choices are interdependent because the connectivity measure shapes topology, the threshold changes measurable structure, and desired topology constrains earlier choices.
  • Limitations: Functional-network analysis is subjective without governing rules, including when researchers choose thresholds based mainly on experience.
  • Extensions: Network analysis has expanded beyond static single-layer graphs to address temporal edges and multiple connection types.

Data Mining tasks and models

Data mining tasks divide into predictive and descriptive approaches. Predictive models infer labels or values, while descriptive models characterize data through clusters, associations, trends, and anomalies.

  • Task types: Data mining tasks are classified as predictive, which infer patterns for future predictions, or descriptive, which characterize general data properties.
  • Descriptive modelling: Descriptive modelling explores existing data relations without forecasting, mainly using clustering and association-rule techniques.
  • Descriptive modelling: Clustering groups similar records and separates dissimilar ones according to similarity measures.
  • Clustering methods: Hierarchical, partition-based, and density-based methods form distinct clustering families, including dendrograms, K-means, and DBSCAN.
  • Descriptive modelling: Association-rule mining identifies attribute-value conditions that frequently occur together and supports applications such as market-basket analysis.
  • Predictive modelling: Predictive modelling learns from labelled training data to predict a target attribute, including numeric values or discrete class labels.

Algorithms and models

Data-mining models include regression, logistic regression, Bayesian and decision-tree methods, random forests, and other classifiers, each suited to different data and modelling requirements.

  • Algorithm overview: Classification algorithms differ in their advantages, disadvantages, and requirements for data format, so model choice depends on the problem.Figure 3 illustrates linear regression, kNN, SVM, decision trees, and artificial neural networks as selected classification algorithms.
  • Regression: Regression estimates relationships among variables by fitting a linear function and minimising a cost function during training.Multivariate regression can overfit when many features allow the model to fit training data but generalise poorly.
  • Logistic regression: Logistic regression models a binary outcome probability as a function of predictors and estimates unknown parameters by maximum likelihood.Its decision boundary is defined by β0+xβ = 0, predicting class 1 for non-negative values and class 0 otherwise.
  • Probabilistic models: Bayesian networks represent conditional dependencies among random variables with a directed acyclic graph and node-specific probability functions.Naïve Bayes classifiers use feature-independence assumptions and scale linearly with the number of variables.
  • Decision trees: Decision trees recursively split records using attribute tests until subsets become class-homogeneous, with criteria such as information gain or the Gini index.They can handle numerical and categorical variables with little data preparation.
  • Random forests: Random forests combine many tree predictors, using bootstrap samples and random feature subsets at each node before growing trees without pruning.The review identifies resistance to overfitting and strong accuracy as two important advantages.

Feature selection

Feature selection chooses a subset of variables for subsequent analysis, supporting data understanding, faster training, prediction performance, and dimensionality management.

  • Purpose and scope: Feature selection discards features expected to be irrelevant and is especially useful when datasets contain many variables but few records.The review highlights gene and protein expression, chemistry, and text classification as examples of such settings.
  • Method families: Feature-selection methods comprise filters, wrappers, and embedded techniques.These families differ in whether selection is independent of the predictor, evaluated through predictor performance, or integrated into training.
  • Filters: Filters select variables during preprocessing, independently of the chosen predictor, with Recursive Feature Elimination as a representative example.RFE repeatedly constructs a model and removes features with low weights.
  • Wrappers: Wrappers evaluate feature subsets by running a predictive model while searching through possible combinations of variables.The learning algorithm is treated as a black box that scores candidate subsets.
  • Embedded methods: Embedded methods optimise model fit together with a penalty for using many variables, performing selection during training.They are usually specific to particular learning algorithms.

Validation

Validation evaluates predictive capability and compares models while accounting for generalisation error, overfitting, and uncertainty from limited datasets.

  • Validation goals: Validation covers performance-evaluation metrics and methods for comparing competing models.This review focuses on evaluating predictive capability rather than statistical model comparison.
  • Error types: Training error measures performance on the training set, whereas generalisation error measures performance on unseen data and may be substantially larger.The gap commonly reflects overfitting, especially with small or unrepresentative datasets and complex models.
  • Hold-out validation: The hold-out method splits data into training and validation subsets, typically using two thirds for training and one third for testing.Accuracy is the proportion of correctly classified instances, while error rate is the proportion of incorrect predictions.
  • Cross-validation: k-fold cross-validation partitions the sample into k equal subsamples, trains on k−1 folds, tests on the remaining fold, and averages error rates across validation sets.It is presented as a more complete and reliable method for estimating extra-sample error.

Data mining software

The section surveys data-mining tools and illustrates how data mining and complex-network analysis can be combined to extract and classify information from complex systems.

  • Weka is a free Java collection of machine-learning algorithms that can run on data files or from Java programs.
  • KNIME is a free graphical data-analytics platform based on Weka libraries, covering data access, transformation, predictive analytics, and visualisation.
  • R provides a free environment for statistical computing and graphics, whereas SAS is a commercial suite for advanced analytics and predictive applications.
  • In a flower-inheritance example, a decision-tree model predicted offspring colour with an 18.6% error rate under Leave-One-Out cross-validation.
  • Accurate abstraction requires the input data to contain all elements needed to recover the target theory; missing parameters cannot be supplied by the algorithm.

3. Classification

This section examines classification with complex-network representations, showing why statistical significance and direct data mining alone may be insufficient and how network metrics support biomedical classification.

  • Classification creates models that predict the class of unseen instances, with applications including medical diagnostic tools.
  • 3.1. Statistics vs. classification: A statistically significant difference between groups does not necessarily enable successful classification, while small samples can permit classification without a significant p-value.For µ = 1.0, p-value is approximately 10^-30 while classification error remains around 40%; below 20 subjects, classification can succeed despite insufficient statistical significance.
  • 3.1. Statistics vs. classification: Statistical significance and classification performance should therefore be assessed together, especially for diagnostic applications and small biomedical datasets.
  • 3.2. Are network metrics really necessary?: An Artificial Neural Network could not recover efficiency or clustering coefficient from adjacency matrices of random networks, with every coefficient of determination R2 below 0.04.The experiment used 20,000 random ten-node networks with fixed link density p = 0.3.
  • 3.2. Are network metrics really necessary?: The experiment demonstrates that one data-mining algorithm is generally insufficient for representing the structure of a sufficiently complex system.
  • Complex-network metrics have supported classification across neuroscience, connectomics, and omics applications, including 87.5% accuracy for autistic subjects and 75%–81% AUC for lethal genes.Reported examples use functional or structural network features with classifiers such as SVMs, decision trees, and multiple combined classifiers.

4. Improving network significance

This section shows how data mining can guide the selection of synchronisation metrics, thresholds, and network features for improving network-based classification. These strategies can improve scores, but may be computationally costly and leave explanatory questions unresolved.

  • Guided network construction: Data mining can guide the joint selection of synchronisation metrics, thresholds, and topological metrics using a global classification objective.The goal is to identify rules for choosing the combination that best serves the task.
  • Threshold selection: Classification scores can serve as a proxy for the significance of binarised networks when selecting an optimal threshold.Networks generated across a range of densities are classified, and the threshold with the highest score is selected.
  • Limitations: Threshold optimisation is computationally costly and yields a single threshold, preventing integration of information across different densities.The review also leaves unanswered why low thresholds, linear correlation, and Decision Trees perform better in the reported task.
  • Integrated selection: Multikernel SVM can select topological features and thresholds simultaneously, integrating information across the analysis pipeline.This approach addresses the joint selection problem rather than choosing each element separately.
  • Hands-on comparison: 77.5% was the best score for a Decision Tree at threshold 0.45, compared with 63% at threshold 0.75.The Decision Tree was most efficient for almost any threshold among the five evaluated models.
  • Synchronisation metrics: Granger Causality reached its maximum with a Decision Tree near threshold 0.35, but scored significantly below linear correlation.The review states that Granger Causality captured information propagation that was not relevant to distinguishing the groups.

5. Feature selection

Feature selection addresses the computational and statistical problems created by high-dimensional data. In network analysis, it can reduce the set of nodes and links, while network structure can also support feature selection in arbitrary data sets.

  • Motivation: High-dimensional feature spaces can make data-mining algorithms scale poorly when many irrelevant features are included.Feature selection aims to reduce computational cost, focus analysis on relevant data, and improve data-set quality.
  • Motivation: Feature selection is especially important when many variables are measured from few samples, as in gene expression and MEG or EEG recordings.These settings combine high dimensionality with limited observations.
  • Network applications: In network analysis, data mining can reduce problem dimensionality by selecting a smaller set of nodes and links.The review also considers the converse use of complex networks for selecting features from arbitrary data sets.
  • Application scope: Node selection is examined across neuroscience, omics analysis, and other complex systems.The section frames these as three application areas in which selection can be useful despite the ideal of retaining all nodes.

Neuroscience

Neuroscience applications use feature selection to make very large brain networks tractable and potentially improve classification. The review discusses anatomical grouping and data-mining alternatives, while noting that their comparative usefulness remains unsettled.

  • fMRI dimensionality: fMRI can involve 10^5 voxels, producing adjacency matrices with 10^10 elements and requiring about 10 GB of memory.Pairwise synchronisation also creates many statistical tests requiring correction for multiple comparisons.
  • Anatomical reduction: Anatomical grouping reduces fMRI nodes but can underestimate node connectivity and overestimate clustering degree.The resulting network properties may differ from those obtained without grouping voxels.
  • Data-mining methods: Data-mining alternatives include Recursive Feature Elimination, forward strategies using Mutual Information, and regularisation trees.These methods have been applied to functional imaging and fMRI node selection.
  • Classification impact: Node selection is expected to improve the reliability and precision of subsequent classification, but its advantage over prior anatomical knowledge remains debated.Some studies report increased classification scores, while the review describes the broader comparison as unresolved.
  • Other modalities: EEG and MEG usually have 60–250 channels, making dimensionality less problematic than in fMRI, though some applications can still benefit from node reduction.Brain-Computer Interface applications are given as an example.

Omics analysis

Omics analysis applies feature selection and network construction to high-dimensional molecular data. The review describes backward elimination, spectral-network methods, and clustering, while noting limitations of hierarchical clustering.

  • High-dimensional omics: Genomics, proteomics, and metabolomics offer promising applications but require analysis of high-dimensional data spaces.Functional genetic networks can be built from gene-expression patterns and pairwise correlations or related measures.
  • Feature elimination: Sequential Backward Selection starts with the full feature set and repeatedly removes the least relevant feature until a stopping condition is met.This is a top-down dimensionality-reduction strategy.
  • Spectral networks: Mutual Information can support network construction from spectral frequencies instead of standard non-overlapping spectral bins.The review presents this as an alternative way to analyse raw omics data.
  • Clustering: Clustering can identify groups of omics elements with similar dynamics and represent them using cluster representatives or mean expression levels.k-means and fuzzy c-means are among the commonly used algorithms.
  • Clustering limitations: Hierarchical clustering imposes irreversible grouping restrictions and performs comparatively poorly.Nodes joined in one cluster cannot later be separated and assigned to different clusters.

Other complex systems

Complex networks support analysis of climate and transportation systems by revealing large-scale patterns and identifying relevant nodes beyond an initial regional boundary.

  • Climate networks identify global patterns in high-resolution weather and reanalysis data, supporting deeper understanding of underlying processes and prediction tasks.
  • Transportation-network analysis requires selecting externally connected airports and flights that remain relevant to a region-specific problem.
  • Link sampling filters dense network structures to produce simpler subgraphs that retain key information.

Network-based methods

Network-based methods select informative links and nodes, reconstruct functional relationships, and improve data-mining analyses. Examples include silencing indirect correlations, mutual-information feature selection, protein-interaction assessment, and EEG-based dimensionality reduction.

  • Link selection: Minimum Spanning Trees connect all network nodes with the shortest tree but destroy local cycles and distort clustering structure.
  • Link selection: Surrogate networks preserve distributions and autocorrelation properties while testing whether functional-network links reflect robust time-series statistics.
  • Indirect-link silencing: A matrix transformation converts observed correlations into a silenced matrix whose retained terms represent direct causal links; in E. coli, prediction improved 50% over traditional correlations.
  • Data mining-based link selection: Mutual-information methods select or remove links using triplet-based indirect-interaction tests, relevance–redundancy optimization, or conditional entropy.
  • Protein-interaction networks: LOO-LME assesses protein-interaction reliability through leave-one-out analysis, while fast-ISOMAP ranks interactions using similarity in a low-dimensional metric space.
  • Feature selection: Complex networks can improve feature selection by ranking nodes with centrality metrics or identifying causal nodes after graph-based structure learning.
  • Feature selection: EEG feature reduction preserved classification above 80% after deleting up to ten nodes, leaving nine nodes identified as most important for pathology understanding.
  • Feature selection: Unguided topological features achieved only ≈60%, whereas data mining highlighted relevant synchronization metrics and brain regions, yielding higher prognostic capabilities and better pathology understanding.

6. Additional bridges

The review presents additional bridges between data mining and complex network analysis, including clustering, link prediction, generative-model validation, and semantic graph representations for Big Data.

  • 6.1. Clustering and community detection: Clustering groups similar objects, while community detection identifies densely internally connected node groups; mapping similar objects to network nodes makes the tasks closely related.Network analysis can incorporate the full network topology, provided a suitable similarity metric is available.
  • 6.1. Clustering and community detection: A complex-network approach has historically yielded better clustering results than classical data-mining approaches, including applications to song-cover groups and financial markets.Examples include statistically validated investor networks and clustering stocks using return and volatility correlations.
  • 6.2. Link prediction: Link prediction estimates unobserved relationships in complex networks, addressing settings where only a small fraction of biological links has been experimentally tested.Reported coverage includes 20% of molecular interactions in yeast and 0.3% in humans.
  • 6.2. Link prediction: Link prediction in network theory corresponds to recommendation systems in data mining, although the two fields historically emphasized different methodological approaches.Network studies relied more on random walks and maximum-likelihood methods, while recommender systems commonly used Markov chains and statistical models.
  • 6.3. Evaluating and validating generative models: Generative network models must be optimized for topological equivalence and validated because matching topology alone does not guarantee representation of the underlying biological process.The review connects this validation problem to improving network significance.
  • 6.4. Complex networks in Big Data: semantic representations by graphs: A Big Data framework transforms raw information into RDF triples, then uses graph tools to create directed labelled graphs for visual and further analysis.In the cardiovascular example, larger “Obese” and “Overweight” node degrees indicate that most subjects have some overweight problems.
  • 6.4. Complex networks in Big Data: semantic representations by graphs: The semantic graph approach faces a scalability challenge when handling and representing very large data sets, though tools such as NodeXL reduce its relevance in many applications.The framework is intended to control data variety and semantic heterogeneity while producing graph representations.

7. Conclusions

The review concludes that data mining and complex networks provide complementary viewpoints and can broaden quantitative analysis of complex systems. It also identifies methodological, theoretical, computational, and software challenges that constrain further integration.

  • 7. Conclusions: Data mining and network theory share the objective of representing complex systems, while offering different viewpoints for describing their structure and dynamics.The review presents their combination as a source of cross-fertilization across applications.
  • 7. Conclusions: Data mining can improve network representations by identifying important nodes and connections, discriminating between groups, and estimating reconstructed-network significance.These capabilities support diagnostic and prognostic applications.
  • 7. Conclusions: Network representations give data scientists a way to structure information and describe systems through quantitative variables, while shared problems such as clustering and recommendation systems invite cross-fertilization.The review also anticipates increasing interest in network theory for Big Data, where relationships are fundamental.
  • 7.1. Problems to overcome: Integration is constrained by pitfalls from mismatched assumptions and limitations, alongside a lack of specific theoretical and numerical foundations for combining the fields.The authors identify these as issues requiring further work.
  • 7.1. Problems to overcome: Data-mining algorithm and validation choices materially affect results, so papers should specify these choices and treat algorithm selection as a fundamental methodological step.Different classifiers make different pattern assumptions, and validation strategies can expose model limitations.
  • 7.1. Problems to overcome: Using one data-mining technique can provide only a partial picture, because different classification models may produce different accuracies even on similar data sets.The review recommends comparing algorithms and selecting the best-performing one while examining why results differ.
  • 7.1. Problems to overcome: Feature selection and classification on the same class-informed data can cause overfitting, motivating separation of training, validation, and test data.The problem arises when filtering uses information about the final class outcome.

Final note

The final note lists additional recent references related to the review’s topics, including heterogeneous network representations, network embedding, clustering, anomaly detection, topology, temporal communities, and Big Data network filtering.

  • Final note: Additional references cover general frameworks for heterogeneous complex systems across scales and machine-learning methods for efficient network embedding in hyperbolic space.
  • Final note: The list also includes work on clustering data sets with complex-network analysis and graph-based anomaly detection and description.
  • Final note: Other cited topics include topological strata, community structure and activity patterns in temporal networks, and network filtering methods for Big Data.

Appendix A. List of acronyms

The appendix defines acronyms and abbreviations used throughout the review, including ANN, AUC, BCI, and EEG.

  • Appendix A. List of acronyms: ANN denotes Artificial Neural Network, AUC denotes Area Under the Curve, BCI denotes Brain-Computer Interfaces, and EEG denotes ElectroEncephaloGram.
Loading 1604.08816v2…