TL;DR
This paper introduces a novel method, DDQC, for extracting fixed-length feature vectors from network degree distributions. This method effectively captures network similarities and dissimilarities, outperforming existing techniques in classification and clustering tasks, especially for networks of varying sizes.
What Problem Does This Paper Address?
Complex networks are ubiquitous, and understanding their structure and evolution is crucial. The degree distribution, which describes the number of connections each node has, is a fundamental characteristic. However, comparing and analyzing these distributions, especially for networks of different sizes, is challenging. Existing methods like the Kolmogorov-Smirnov test or fitting power-law exponents have significant limitations: they are either too sensitive to network size, assume specific distribution models that don't always hold, or fail to capture nuanced similarities. This paper addresses the need for a robust, size-invariant method to extract meaningful features from degree distributions for tasks like network classification, clustering, and anomaly detection.
Methods
The core of the proposed method, DDQC (Degree Distribution Quantification and Comparison), lies in its feature extraction technique. Instead of relying on global distribution properties or assumptions, DDQC divides the range of node degrees into eight intervals based on the mean and standard deviation of the degrees. The probability of a node's degree falling into each of these intervals (Interval Degree Probability or IDPG) is calculated. This results in an eight-dimensional feature vector for each network's degree distribution.
For comparing two networks, DDQC uses a simple distance function that sums the absolute differences between the corresponding IDPG values of their feature vectors. This approach is designed to be less sensitive to network size and to capture the shape and spread of the degree distribution more effectively than previous methods.
Datasets
The authors evaluated their method using two types of datasets:
- Artificial Networks: A dataset of 6,000 networks generated using six different generative models (Barabási-Albert, Erdős-Rényi, Forest Fire, Kronecker, random power-law, and Watts-Strogatz). The similarity witness here is the generative model itself, assuming networks from the same model share similar degree distributions.
- Real-world Networks: A collection of 33 real-world networks from various categories (citation, collaboration, communication, friendship, peer-to-peer, and web graphs). The similarity witness here is the network category, assuming networks within the same category have similar link formation processes and thus similar degree distributions.
Key Insights and Ideas
- Size Invariance is Crucial: The paper highlights that comparing degree distributions directly without considering network size can be misleading. Normalizing features based on mean and standard deviation is key to achieving meaningful comparisons across networks of different scales.
- Beyond Power-Laws: Many real-world networks do not strictly follow power-law distributions. The proposed method's ability to work without assuming a specific distribution model makes it more broadly applicable.
- Eight Intervals Capture Nuance: Dividing the degree distribution into eight carefully chosen intervals, informed by statistical properties (mean and standard deviation), proves effective in capturing the distribution's shape and characteristics.
- Feature Extraction for Downstream Tasks: The extracted feature vectors are not just for comparison but are valuable inputs for standard machine learning algorithms, enabling network classification and clustering.
Key Results
The DDQC method consistently outperformed baseline methods (KS-test, Percentiles, and Power-law exponent) across several evaluation criteria:
- kNN Accuracy: DDQC achieved the highest average kNN accuracy in classifying both real-world and artificial networks, indicating its ability to extract features that best distinguish network types.
- Precision-at-K (P@K): Similarly, DDQC showed superior performance in P@K, suggesting that its features lead to more accurate identification of nearest neighbors.
- Dunn Index: The method yielded the largest Dunn index, signifying better separation between clusters of similar networks and tighter clusters of dissimilar networks.
- SVM Classification: When integrated with other network features (clustering coefficient, path length, assortativity, modularity), DDQC-derived features significantly improved SVM classification accuracy, demonstrating their informativeness.
Limitations and Future Work
- Limitations: The paper acknowledges that while the category of networks is used as a similarity witness, it's possible for networks of different classes to be more similar than those of the same class. The proposed method relies on this assumption for evaluation.
- Future Work: The authors plan to integrate the quantified degree distribution features into a more comprehensive distance metric for complex networks. This integrated metric will be a foundation for future research in evaluating and selecting network generative models and sampling methods.
Summary updated