iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s10618-023-00975-z
Community detection in interval-weighted networks | Data Mining and Knowledge Discovery Skip to main content
Log in

Community detection in interval-weighted networks

  • Published:
Data Mining and Knowledge Discovery Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Algorithm 1
Algorithm 2
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. 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).

  2. 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] \).

  3. NUTS–Nomenclature of Territorial Units for Statistics (Eurostat 2016).

  4. For the sake of visualization, we chose not to represent the intervals on the network edges, such as it is depicted in Fig. 8d.

  5. 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.

  6. According to various authors, the flows of annual merchandise trade can be conceived as a network (Barigozzi et al. 2011; Traag 2014).

  7. 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 ]\).

  8. For the sake of visualization, we chose not to represent the intervals on the network edges, such as it is depicted in Fig. 8d.

  9. 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

    Google Scholar 

  • 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

    Article  MathSciNet  PubMed  Google Scholar 

  • Alves H, Brito P, Campos P (2022) Centrality measures in interval-weighted networks. J Complex Netw 10(4):1–28

    MathSciNet  CAS  Google Scholar 

  • Arenas A, Duch J, Fernandez A, Gomez S (2007) Size reduction of complex networks preserving modularity. New J Phys 9(6):176

    Article  MathSciNet  Google Scholar 

  • Barigozzi M, Fagiolo G, Mangioni G (2011) Identifying the community structure of the international-trade multi-network. Phys A 390(11):2051–2066

    Article  CAS  Google Scholar 

  • Billard L, Diday E (2007) Symbolic Data Analysis: Conceptual Statistics and Data Mining. Wiley Series in Computational Statistics. Wiley, West Sussex

    Google Scholar 

  • Blondel VD, Guillaume JL, Lambiotte R, Etienne L (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 10:P10008

    Article  Google Scholar 

  • Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D (2006) Complex networks: structure and dynamics. Phys Rep 424(4–5):175–308

    Article  ADS  MathSciNet  Google Scholar 

  • 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

    Article  Google Scholar 

  • Bryant V (1985) Metric spaces. Iteration and application. Cambridge University Press, Cambridge

    Book  Google Scholar 

  • Chakraborty T, Dalmia A, Mukherjee A, Ganguly N (2017) Metrics for community analysis: a survey. ACM Comput Surv 50(4):1–47

    Article  Google Scholar 

  • 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

    Article  MathSciNet  Google Scholar 

  • Clauset A, Newman ME, Moore C (2004) Finding community structure in very large networks. Phys Rev E 70(6):066111

    Article  ADS  Google Scholar 

  • Clauset A, Moore C, Newman MEJ (2008) Hierarchical structure and the prediction of missing links in networks. Nature 453:98–101

    Article  ADS  CAS  PubMed  Google Scholar 

  • 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

    Google Scholar 

  • Couso I, Dubois D (2014) Statistical reasoning with set-valued information: ontic vs. epistemic views. Int J Approx Reason 55(7):1502–1518

    Article  MathSciNet  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  MathSciNet  Google Scholar 

  • Dijkstra EW (1959) A note on two problems in connection with graphs. Numer Math 1:269–271

    Article  MathSciNet  Google Scholar 

  • 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

    Article  MathSciNet  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  ADS  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Ford LR, Fulkerson DR (1962) Flows in networks. Princeton University Press, Princeton

    Google Scholar 

  • Fortunato S, Hric D (2016) Community detection in networks: a user guide. Phys Rep 659:1–44

    Article  ADS  MathSciNet  Google Scholar 

  • 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

    Article  MathSciNet  Google Scholar 

  • Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826

    Article  ADS  MathSciNet  CAS  PubMed  PubMed Central  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  MathSciNet  Google Scholar 

  • 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

    Article  ADS  PubMed  PubMed Central  Google Scholar 

  • Hossain A (2012) A polynomial interval shortest-route algorithm for acyclic network. Inf Technol Control 4:2–8

    Google Scholar 

  • Hossain A, Gatev G (2010) Method and algorithm for interval maximum expected flow in a network. Inf Technol Control 1:18–24

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  PubMed  Google Scholar 

  • 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

    Article  ADS  CAS  PubMed  Google Scholar 

  • Lancichinetti A, Fortunato S (2009) Community detection algorithms: a comparative analysis. Phys Rev E 80(5):161

    Article  Google Scholar 

  • Lancichinetti A, Radicchi F, Ramasco JJ, Fortunato S (2011) Finding statistically significant communities in networks. PLoS ONE 6(4):e18961

    Article  ADS  CAS  PubMed  PubMed Central  Google Scholar 

  • Martin T, Ball B, Newman MEJ (2016) Structural inference for uncertain networks. Phys Rev E 93(1):012306

    Article  ADS  PubMed  Google Scholar 

  • Moore RE (1979) Methods and applications of interval analysis. SIAM, Philadelphia

    Book  Google Scholar 

  • Moore RE, Kearfott RB, Cloud MJ (2009) Introduction to interval analysis. SIAM, Philadelphia

    Book  Google Scholar 

  • Nayeem S, Pal M (2005) Shortest path problem on a network with imprecise edge weight. Fuzzy Optim Decis Making 4:293–312

    Article  MathSciNet  Google Scholar 

  • 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

    MathSciNet  Google Scholar 

  • Newman M (2003) The structure and function of complex networks. SIAM Rev 45:167–256

    Article  ADS  MathSciNet  Google Scholar 

  • 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

    Book  Google Scholar 

  • Newman MEJ (2018) Networks, 2nd edn. Oxford University Press, Oxford

    Book  Google Scholar 

  • Newman ME, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69(2):026113

    Article  ADS  CAS  Google Scholar 

  • Noirhomme-Fraiture M, Brito P (2011) Far beyond the classical data models: symbolic data analysis. Stat Anal Data Min 4(2):157–170

    Article  MathSciNet  Google Scholar 

  • Okada S, Gen M (1993) Order relation between intervals and its application to shortest path problem. Comput Ind Eng 25:147–150

    Article  Google Scholar 

  • Palla G, Derényi I, Vicsek T (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435:814–818

    Article  ADS  CAS  PubMed  Google Scholar 

  • Rokne J (2001) Interval arithmetic and interval analysis: an introduction. In: Pedrycz W (ed) Granular computing: an emerging paradigm. Physica, Heidelberg, pp 1–22

    Google Scholar 

  • Rostami R, Ebrahimnejad A (2016) On solving maximum and quickest interval-valued flows over time. J Intell Fuzzy Syst 30:347–358

    Article  Google Scholar 

  • 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

    Article  MathSciNet  Google Scholar 

  • 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

    Article  Google Scholar 

  • Sengupta A, Pal TK (2006) Solving the shortest path problem with interval arcs. Fuzzy Optim Decis Making 5(1):71–89

    Article  MathSciNet  Google Scholar 

  • Sengupta A, Pal TK (2009) Fuzzy preference ordering of interval numbers in decision problems. Springer, Berlin

    Book  Google Scholar 

  • Traag V (2014) Algorithms and dynamical models for communities and reputation in social networks. Springer, Heidelberg

    Book  Google Scholar 

  • Traag VA (2015) Faster unfolding of communities: speeding up the Louvain algorithm. Phys Rev E 92(3):032801

    Article  ADS  CAS  Google Scholar 

  • Traag VA, Bruggeman J (2009) Community detection in networks with positive and negative links. Phys Rev E 80(3):036115

    Article  ADS  CAS  Google Scholar 

  • 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

    Book  Google Scholar 

  • 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

    Article  Google Scholar 

  • Zadeh LA (1965) Fuzzy sets. Inf Control 8:338–353

    Article  Google Scholar 

  • 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

    Article  ADS  CAS  PubMed  PubMed Central  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to Hélder Alves.

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

figure i

Appendix B: R output for Method 2. Hybrid Louvain (HL)—Intervals Midpoint

figure j

Appendix C: Adjacency matrices for the interval-weighted network (IWN) obtained from the aggregation method used.

Method 1. Classic Louvain (CL)

Table 6 Interval-weighted adjacency matrix for the three communities \((C_1,C_2\ \text {and}\ C_3)^{\textrm{a}}\)—Method 1. Classic Louvain (CL)

Method 2. Hybrid Louvain (HL)

Table 7 Interval-weighted adjacency matrix for the three communities \((C_1,C_2\ \text {and}\ C_3)^{\textrm{a}}\)—Method 2. Hybrid Louvain (HL)

Appendix D: Community structure according to Louvain’s Method—Degenerate Intervals of midpoints (IWCN)

Table 8 Summary of the outcomes obtained for the weighted Commuters Network (intervals midpoint), according to Louvain’s algorithm
Fig. 13
figure 13

On the left of the sketch for both methods is represented the final weighted network with super-vertices, followed on the right by the geographical representation of communities at level 1 (end of first pass) of the LA, the Dendrogram for the Louvain’s community detection process and, the geographical representation of communities at level 2 (end of second pass) of the LA

Table 9 Summary of the outcomes obtained for the weighted Trade Network (intervals midpoint), according to Louvain’s algorithm

Appendix E: Community structure according to Louvain’s Method—Degenerate Intervals of midpoints (IWTN)

Fig. 14
figure 14

Geographical representation of the communities according the Classical Louvain algorithm to the case of degenerate intervals—weighted network

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10618-023-00975-z

Keywords

Navigation