Abstract
Real-world networks typically display a complex structure that is hard to explain by a single model. A common approach is to partition the edges of the network into disjoint simpler structures. An important property in this context is locality—incident vertices usually have many common neighbors. This allows to classify edges into two groups, based on the number of the common neighbors of their incident vertices. Formally, this is captured by the common-neighbors (CN) metric, which forms the basis of many metrics for detecting outlier edges. Such outliers can be interpreted as noise or as a substructure.
We aim to understand how useful the metric is, and empirically analyze several scenarios. We randomly insert outlier edges into real-world and generated graphs with high locality, and measure the metric accuracy for partitioning the combined edges. In addition, we use the metric to decompose real-world networks, and measure properties of the partitions. Our results show that the CN metric is a very good classifier that can reliably detect noise up to extreme levels (83% noisy edges). We also provide mathematically rigorous analyses on special random-graph models. Last, we find the CN metric consistently decomposes real-world networks into two graphs with very different structures.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aggarwal, C.C.: Outlier Detection in Graphs and Networks, pp. 369–397 (2017)
Aggarwal, C.C., He, G., Zhao, P.: Edge classification in networks. In: ICDE, pp. 1038–1049 (2016)
Albert, R., Barabási, A.L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002)
Bläsius, T., Fischbeck, P.: On the external validity of average-case analyses of graph algorithms. In: 30th Annual European Symposium on Algorithms (ESA 2022), vol. 244, pp. 21:1–21:14 (2022). https://doi.org/10.4230/LIPIcs.ESA.2022.21
Bläsius, T., Fischbeck, P.: On the External Validity of Average-Case Analyses of Graph Algorithms (Data, Docker, and Code), May 2022
Chakrabarti, D.: AutoPart: parameter-free graph partitioning and outlier detection. In: Boulicaut, J.-F., Esposito, F., Giannotti, F., Pedreschi, D. (eds.) PKDD 2004. LNCS (LNAI), vol. 3202, pp. 112–124. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30116-5_13
Csardi, G., Nepusz, T.: The igraph software package for complex network research. InterJournal Complex Systems, 1695 (2006)
Erdős, P., Rényi, A.: On random graphs I. Publicationes Mathematicae 6, 290–297 (1959)
Hautamaki, V., Karkkainen, I., Franti, P.: Outlier detection using k-nearest neighbour graph. In: ICPR, vol. 3, pp. 430–433 (2004)
Kou, Y., Lu, C.T., Dos Santos, R.F.: Spatial outlier detection: a graph-based approach. In: ICTAI, vol. 1, pp. 281–288 (2007)
Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., Boguñá, M.: Hyperbolic geometry of complex networks. Phys. Rev. E 82, 036106 (2010)
Lü, L., Zhou, T.: Link prediction in complex networks: a survey. Physica A 390(6), 1150–1170 (2011)
Mansour, R.F., Abdel-Khalek, S., Hilali-Jaghdam, I., Nebhen, J., Cho, W., Joshi, G.P.: An intelligent outlier detection with machine learning empowered big data analytics for mobile edge computing. Clust. Comput. (2021)
Newman, M., Barabási, A., Watts, D.: The Structure and Dynamics of Networks. Princeton Studies in Complexity, Princeton University Press (2011)
Pandhre, S., Gupta, M., Balasubramanian, V.N.: Community-based outlier detection for edge-attributed graphs. CoRR abs/1612.09435 (2016)
Penrose, M.: Random Geometric Graphs, vol. 5. OUP Oxford (2003)
Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: AAAI (2015)
Schaeffer, S.E.: Graph clustering. Comput. Sci. Rev. 1(1), 27–64 (2007)
Staudt, C.L., Sazonovs, A., Meyerhenke, H.: NetworKit: a tool suite for large-scale complex network analysis (2015)
Suri, N.N.R.R., Murty, N.M., Athithan, G.: Outlier Detection: Techniques and Applications. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-05127-3
Zhang, H., Kiranyaz, S., Gabbouj, M.: Outlier edge detection using random graph generation models and applications. J. Big Data 4(1), 1–25 (2017). https://doi.org/10.1186/s40537-017-0073-8
Zhang, H., Kiranyaz, S., Gabbouj, M.: Data clustering based on community structure in mutual k-nearest neighbor graph. In: TSP, pp. 1–7 (2018)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Cohen, S., Fischbeck, P., Friedrich, T., Krejca, M. (2023). The Common-Neighbors Metric Is Noise-Robust and Reveals Substructures of Real-World Networks. In: Kashima, H., Ide, T., Peng, WC. (eds) Advances in Knowledge Discovery and Data Mining. PAKDD 2023. Lecture Notes in Computer Science(), vol 13935. Springer, Cham. https://doi.org/10.1007/978-3-031-33374-3_6
Download citation
DOI: https://doi.org/10.1007/978-3-031-33374-3_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-33373-6
Online ISBN: 978-3-031-33374-3
eBook Packages: Computer ScienceComputer Science (R0)