Abstract
In this paper we introduce and develop the concept of interval-weighted networks (IWN), a novel approach in Social Network Analysis, where the edge weights are represented by closed intervals composed with precise information, comprehending intrinsic variability. We extend IWN for both Newman’s modularity and modularity gain and the Louvain algorithm, considering a tabular representation of networks by contingency tables. We apply our methodology to two real-world IWN. The first is a commuter network in mainland Portugal, between the twenty three NUTS 3 Regions (IWCN). The second focuses on annual merchandise trade between 28 European countries, from 2003 to 2015 (IWTN). The optimal partition of geographic locations (regions or countries) is developed and compared using two new different approaches, designated as “Classic Louvain” and “Hybrid Louvain” , which allow taking into account the variability observed in the original network, thereby minimizing the loss of information present in the raw data. Our findings suggest the division of the twenty three Portuguese regions in three main communities for the IWCN and between two to three country communities for the IWTN. However, we find different geographical partitions according to the community detection methodology used. This analysis can be useful in many real-world applications, since it takes into account that the weights may vary within the ranges, rather than being constant.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
The term interval-weighted network strickly means that the weights associated with edges are interval valued, i.e., the order of vertices is not taking into consideration (Hu and Hu 2007).
It should be noted that the subtraction of two equal intervals is not \(\left[ {0}, {0}\right] \) (except for degenerate intervals). This is because \(X-X=\{x-y:x \in X,\, y \in X \}\), rather than \(\{x-x:x \in X\}\) (Jaulin et al. 2001). For example, \(\left[ {1}, {2}\right] -\left[ {1}, {2}\right] =\left[ {-1}, {1}\right] \).
NUTS–Nomenclature of Territorial Units for Statistics (Eurostat 2016).
For the sake of visualization, we chose not to represent the intervals on the network edges, such as it is depicted in Fig. 8d.
It is important to highlight the fact that the numerical values for the different modularities (\(Q^{I}\), \(Q^{I}_{norm}\) and \(Q^{I}_{\max }\)) are not comparable since different mathematical procedures are used in each method.
Analogously to the procedure adopted for the IWCN in Subsection 5.1 (see Figs. 8a and 8b), where the elements \(o^I_{ij}\) of the symmetric interval-weighted adjacency matrix, \(O^I\), denote the maximum variability of the bi-directional flows ij and ji between the countries i and j (Fig. 8b): \(o^I_{ij}=\big [\min \{\underline{o}'_{ij},\underline{o}''_{ji}\},\max \{\overline{o}'_{ij},\overline{o}''_{ji}\}\big ]=\big [\underline{o}_{ij},\overline{o}_{ij}\big ]\).
For the sake of visualization, we chose not to represent the intervals on the network edges, such as it is depicted in Fig. 8d.
The other Baltic country, Estonia, was not part of the data.
References
Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows. Theory, algorithms, and applications. Prentice Hall, New Jersey
Ak R, Vitelli V, Zio E (2015) An interval-valued neural network approach for uncertainty quantification in short-term wind speed prediction. IEEE Trans Neural Netw Learn Syst 26(11):2787–2800
Alves H, Brito P, Campos P (2022) Centrality measures in interval-weighted networks. J Complex Netw 10(4):1–28
Arenas A, Duch J, Fernandez A, Gomez S (2007) Size reduction of complex networks preserving modularity. New J Phys 9(6):176
Barigozzi M, Fagiolo G, Mangioni G (2011) Identifying the community structure of the international-trade multi-network. Phys A 390(11):2051–2066
Billard L, Diday E (2007) Symbolic Data Analysis: Conceptual Statistics and Data Mining. Wiley Series in Computational Statistics. Wiley, West Sussex
Blondel VD, Guillaume JL, Lambiotte R, Etienne L (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 10:P10008
Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D (2006) Complex networks: structure and dynamics. Phys Rep 424(4–5):175–308
Brito P (2014) Symbolic Data Analysis: another look at the interaction of Data Mining and Statistics. Wiley Interdiscipl Rev Data Min Knowl Discov 4(4):281–295
Bryant V (1985) Metric spaces. Iteration and application. Cambridge University Press, Cambridge
Chakraborty T, Dalmia A, Mukherjee A, Ganguly N (2017) Metrics for community analysis: a survey. ACM Comput Surv 50(4):1–47
Chen Y, Wang X, Xiang X, Tang B, Chen Q, Fan S, Bu J (2017) Overlapping community detection in weighted networks via a Bayesian approach. Phys A 468:790–801
Clauset A, Newman ME, Moore C (2004) Finding community structure in very large networks. Phys Rev E 70(6):066111
Clauset A, Moore C, Newman MEJ (2008) Hierarchical structure and the prediction of missing links in networks. Nature 453:98–101
Comber AJ, Brunsdon CF, Farmer CJQ (2012) Community detection in spatial networks: inferring land use from a planar graph of land cover objects. Int J Appl Earth Observ Geoinf 18:274–282
Couso I, Dubois D (2014) Statistical reasoning with set-valued information: ontic vs. epistemic views. Int J Approx Reason 55(7):1502–1518
Dahlin J, Svenson P (2011) A method for community detection in uncertain networks. In: EISIC, pp 155–162
Dawood H (2011) Theories of interval arithmetic. Mathematical foundations and applications. LAP Lambert Academic Publishing, London
De Montis A, Caschili S, Chessa A (2013a) Commuter networks and community detection: a method for planning sub regional areas. Eur Phys J Spec Top 215(1):75–91
De Montis A, Caschili S, Chessa A (2013b) Recent developments of complex network analysis in spatial planning. In: Scherngell T (ed) The geography of networks and R &D collaborations. Advances in spatial science. Springer International Publishing, Berlin, pp 29–47
Diamond P (2001) A fuzzy max-flow min-cut theorem. Fuzzy Sets Syst 119:139–148
Dijkstra EW (1959) A note on two problems in connection with graphs. Numer Math 1:269–271
Ebrahimnejad A (2021) An acceptability index based approach for solving shortest path problem on a network with interval weights. RAIRO Oper Res 55:S1767–S1787
Ebrahimnejad A, Karimnejad Z, Alrezaamiri H (2015) Particle swarm optimisation algorithm for solving shortest path problems with mixed fuzzy arc weights. Int J Appl Decis Sci 8:203–222
Ebrahimnejad A, Tavana M, Alrezaamiri H (2016) A novel artificial bee colony algorithm for shortest path problems with fuzzy arc weights. Measurement 93:48–56
Ebrahimnejad A, Enayattabr M, Motameni H, Garg H (2021) Modified artificial bee colony algorithm for solving mixed interval-valued fuzzy shortest path problem. Complex Intell Syst 7(3):1527–1545
Eurostat (2016) Commission Regulation (EU) 2016/2066 of 21 November 2016 amending the annexes to Regulation (EC) No 1059/2003 of the European Parliament and of the Council on the establishment of a common classification of territorial units for statistics (NUTS). https://ec.europa.eu/eurostat/web/nuts/background. Accessed 15 June 2017
Everitt BS (1992) The analysis of contingency tables, 2nd edn. Mono. Appl. Probab. Stat. Chapman and Hall, London
Farkas I, Abel D, Palla G, Vicsek T (2007) Weighted network modules. New J Phys 9(6):180
Ford LR, Fulkerson DR (1962) Flows in networks. Princeton University Press, Princeton
Fortunato S, Hric D (2016) Community detection in networks: a user guide. Phys Rep 659:1–44
Ghiyasvand M (2011) A New Approach for Solving the Minimum Cost Flow Problem with Interval and Fuzzy Data. Int J Uncertain Fuzziness Knowl Based Syst 19:71–88
Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826
Grzegorzewski P, Śpiewak M (2017) The sign test for interval-valued data. In: Ferraro MB, Giordani P, Vantaggi B, Gagolewski M, Gil MÁ, Grzegorzewski P, Hryniewicz O (eds) Soft methods for data science. SMPS 2016. Advances in intelligent systems and computing. Springer International Publishing, Cham, pp 269–276
Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A (2003) Self-similar community structure in a network of human interactions. Phys Rev E 68(6):440
Hassanzadeh R, Mahdavi I, Mahdavi-Amiri N, Tajdin A (2013) A genetic algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths. Math Comput Model 57:84–99
He M, Glasser J, Pritchard N, Bhamidi S, Kaza N (2020) Demarcating geographic regions using community detection in commuting networks with significant self-loops. PLoS ONE 15(4):e0230941
Hoffmann T, Peel L, Lambiotte R, Jones NS (2020) Community detection in networks without observing edges. Sci Adv 6(4):eaav1478
Hossain A (2012) A polynomial interval shortest-route algorithm for acyclic network. Inf Technol Control 4:2–8
Hossain A, Gatev G (2010) Method and algorithm for interval maximum expected flow in a network. Inf Technol Control 1:18–24
Hu P, Hu C (2007) Fuzzy partial-order relations for intervals and interval weighted graphs. In: IEEE symposium on foundations of computational inteligence (FOCI), pp 120–127
Hu C, Hu P (2008) Interval-weighted graphs and flow networks. In: Hu C, Kearfott RB, Korvin Ad, Kreinovich V (ed) Knowledge processing with interval and soft computing. Springer, London, pp 1–16
Hu C, Kearfott RB (2008) Interval matrices in knowledge discovery. In: Hu C, Kearfott RB, Korvin Ad, Kreinovich V (ed) Knowledge processing with interval and soft computing. Springer, London, pp 1–19
Hu C, Kearfott RB, de Korvin A, Kreinovich V (2008) Knowledge processing with interval and soft computing. Springer, London
Jaulin L, Kieffer M, Didrit O, Walter E (2001) Applied interval analysis. With examples in parameter and state estimation, robust control and robotics. Springer, London
Khosravi A, Nahavandi S, Creighton D, Atiya AF (2011) Lower upper bound estimation method for construction of neural network-based prediction intervals. IEEE Trans Neural Netw 22(3):337–346
Krogan NJ, Cagney G, Yu H, Zhong G, Guo X, Ignatchenko A, Li J, Pu S, Datta N, Tikuisis AP, Punna T, Peregrín-Alvarez JM, Shales M, Zhang X, Davey M, Robinson MD, Paccanaro A, Bray JE, Sheung A, Beattie B, Richards DP, Canadien V, Lalev A, Mena F, Wong P, Starostine A, Canete MM, Vlasblom J, Wu S, Orsi C, Collins SR, Chandran S, Haw R, Rilstone JJ, Gandi K, Thompson NJ, Musso G, St Onge P, Ghanny S, Lam MHY, Butland G, Altaf-Ul AM, Kanaya S, Shilatifard A, O’Shea E, Weissman JS, Ingles CJ, Hughes TR, Parkinson J, Gerstein M, Wodak SJ, Emili A, Greenblatt JF (2006) Global landscape of protein complexes in the yeast Saccharomyces cerevisiae. Nature 440(7084):637–643
Lancichinetti A, Fortunato S (2009) Community detection algorithms: a comparative analysis. Phys Rev E 80(5):161
Lancichinetti A, Radicchi F, Ramasco JJ, Fortunato S (2011) Finding statistically significant communities in networks. PLoS ONE 6(4):e18961
Martin T, Ball B, Newman MEJ (2016) Structural inference for uncertain networks. Phys Rev E 93(1):012306
Moore RE (1979) Methods and applications of interval analysis. SIAM, Philadelphia
Moore RE, Kearfott RB, Cloud MJ (2009) Introduction to interval analysis. SIAM, Philadelphia
Nayeem S, Pal M (2005) Shortest path problem on a network with imprecise edge weight. Fuzzy Optim Decis Making 4:293–312
Nayeem S, Abu M, Pal M (2008) The p-center problem on fuzzy networks and reduction of cost. Iran J Fuzzy Syst 5:1–26
Newman M (2003) The structure and function of complex networks. SIAM Rev 45:167–256
Newman ME (2004a) Fast algorithm for detecting community structure in networks. Phys Rev E 69(6):066133
Newman MEJ (2004b) Analysis of weighted networks. Phys Rev E 70:056131
Newman MEJ (2010) Networks: an introduction. Oxford University Press, New York
Newman MEJ (2018) Networks, 2nd edn. Oxford University Press, Oxford
Newman ME, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69(2):026113
Noirhomme-Fraiture M, Brito P (2011) Far beyond the classical data models: symbolic data analysis. Stat Anal Data Min 4(2):157–170
Okada S, Gen M (1993) Order relation between intervals and its application to shortest path problem. Comput Ind Eng 25:147–150
Palla G, Derényi I, Vicsek T (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435:814–818
Rokne J (2001) Interval arithmetic and interval analysis: an introduction. In: Pedrycz W (ed) Granular computing: an emerging paradigm. Physica, Heidelberg, pp 1–22
Rostami R, Ebrahimnejad A (2016) On solving maximum and quickest interval-valued flows over time. J Intell Fuzzy Syst 30:347–358
Sarzynska M, Leicht EA, Chowell G, Porter MA (2016) Null models for community detection in spatially embedded, temporal networks. J Complex Netw 4(3):363–406
Schaub MT, Delvenne JC, Rosvall M, Lambiotte R (2017) The many facets of community detection in complex networks. Appl Netw Sci 2(1):2–13
Sengupta A, Pal TK (2006) Solving the shortest path problem with interval arcs. Fuzzy Optim Decis Making 5(1):71–89
Sengupta A, Pal TK (2009) Fuzzy preference ordering of interval numbers in decision problems. Springer, Berlin
Traag V (2014) Algorithms and dynamical models for communities and reputation in social networks. Springer, Heidelberg
Traag VA (2015) Faster unfolding of communities: speeding up the Louvain algorithm. Phys Rev E 92(3):032801
Traag VA, Bruggeman J (2009) Community detection in networks with positive and negative links. Phys Rev E 80(3):036115
UNCTAD (2016) Merchandise trade matrix—detailed products, exports in thousands of United States dollars, annual. https://unctadstat.unctad.org/wds/ReportFolders/reportFolders.aspx. Accessed 09 Sept 2016
Wasserman S, Faust K (1994) Social network analysis: methods and applications. Cambridge University Press, Cambridge
Xiang J, Tang YN, Gao YY, Zhang Y, Deng K, Xu XK, Hu K (2015) Multi-resolution community detection based on generalized self-loop rescaling strategy. Phys A 432:127–139
Zadeh LA (1965) Fuzzy sets. Inf Control 8:338–353
Zhang C, Zaïane OR (2018) Detecting local communities in networks with edge uncertainty. In: IEEEE/ACM ASONAM, pp 9–16
Zhao Y, Levina E, Zhu J (2011) Community extraction for social networks. Proc Natl Acad Sci 108(18):7321–7326
Acknowledgements
This work is financed by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia, within project LA/P/0063/2020.
Author information
Authors and Affiliations
Corresponding author
Additional information
Responsible editor: Srinivasan Parthasarathy.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix A: R output for Method 1. Classic Louvain (CL)—Intervals Sum
Appendix B: R output for Method 2. Hybrid Louvain (HL)—Intervals Midpoint
Appendix C: Adjacency matrices for the interval-weighted network (IWN) obtained from the aggregation method used.
Method 1. Classic Louvain (CL)
Method 2. Hybrid Louvain (HL)
Appendix D: Community structure according to Louvain’s Method—Degenerate Intervals of midpoints (IWCN)
Appendix E: Community structure according to Louvain’s Method—Degenerate Intervals of midpoints (IWTN)
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Alves, H., Brito, P. & Campos, P. Community detection in interval-weighted networks. Data Min Knowl Disc 38, 653–698 (2024). https://doi.org/10.1007/s10618-023-00975-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10618-023-00975-z