Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-19T01:29:10.743Z Has data issue: false hasContentIssue false
  • English
  • Français

Distance closures on complex networks

Published online by Cambridge University Press:  30 March 2015

TIAGO SIMAS  and
LUIS M. ROCHA
TIAGO SIMAS
Affiliation:
Cognitive Science Program, Indiana University, Bloomington, IN 47406, USA (e-mail: [email protected])
LUIS M. ROCHA
Affiliation:
Center for Complex Networks and Systems, School of Informatics & Computing, Indiana University, Bloomington, IN 47406, USA Instituto Gulbenkian de Ciencia, Oeiras, Portugal (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

To expand the toolbox available to network science, we study the isomorphism between distance and Fuzzy (proximity or strength) graphs. Distinct transitive closures in Fuzzy graphs lead to closures of their isomorphic distance graphs with widely different structural properties. For instance, the All Pairs Shortest Paths (APSP) problem, based on the Dijkstra algorithm, is equivalent to a metric closure, which is only one of the possible ways to calculate shortest paths in weighted graphs. We show that different closures lead to different distortions of the original topology of weighted graphs. Therefore, complex network analyses that depend on the calculation of shortest paths on weighted graphs should take into account the closure choice and associated topological distortion. We characterize the isomorphism using the max-min and Dombi disjunction/conjunction pairs. This allows us to: (1) study alternative distance closures, such as those based on diffusion, metric, and ultra-metric distances; (2) identify the operators closest to the metric closure of distance graphs (the APSP), but which are logically consistent; and (3) propose a simple method to compute alternative path length measures and corresponding distance closures using existing algorithms for the APSP. In particular, we show that a specific diffusion distance is promising for community detection in complex networks, and is based on desirable axioms for logical inference or approximate reasoning on networks; it also provides a simple algebraic means to compute diffusion processes on networks. Based on these results, we argue that choosing different distance closures can lead to different conclusions about indirect associations on network data, as well as the structure of complex networks, and are thus important to consider.

Keywords

complex networksalgebraic structuresFuzzy Setsfuzzy graphstransitive closuredistance graphssemi-metric graphsAll Pairs Shortest Pathsdiffusion on networkscommunity detection
Type
Research Article
Information
Network Science , Volume 3 , Issue 2 , June 2015 , pp. 227 - 268
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abi-Haidar, A., Kaur, J., Maguitman, A., Radivojac, P., Rechtsteiner, A., Verspoor, K., . . . Rocha, L. M. (2008). Uncovering protein interaction in abstracts and text using a novel linear model and word proximity networks. Genome Biology, 9 (Suppl 2), S11.Google Scholar
Ahn, Y.-Y., Bagrow, J. P., & Lehmann, S. (2010). Link communities reveal multiscale complexity in networks. Nature, 466 (7307), 761–764.Google Scholar
Albert, R., & Barabasi, A.-L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics, 74 (1), 47.Google Scholar
Baeza-Yates, R., Ribiero-Neto, B., & Ribeiro-Neto, B. (1999). Modern information retrieval. Harlow, England: Pearson Education.Google Scholar
Baniamerian, A., & Menhaj, M. (2006). Fuzzy shortest paths in fuzzy graphs. In Reusch, B., (Ed.), Computational intelligence, theory and applications, (pp. 757–764). Berlin Heidelberg: Springer.Google Scholar
Barabasi, A.-L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286 (5439), 509–512.Google Scholar
Barrat, A., Barthelemy, M., Pastor-Satorras, R., & Vespignani, A. (2004a). The architecture of complex weighted networks. Proceedings of the National Academy of Sciences USA, 101, 3747.Google Scholar
Barrat, A., Barthélemy, M., & Vespignani, A. (2004b). Weighted evolving networks: Coupling topology and weight dynamics. Physical Review Letters, 92, 228701.Google Scholar
Behzadnia, P., Zarandi, S., Berangi, R., & Baniamerian, A. (2008). On updating the shortest path in fuzzy graphs. In International Conference on Computational Intelligence for Modelling Control Automation, pp. 1188–1193.Google Scholar
Bertoluzza, C., & Doldi, V. (2004). On the distributivity between t-norms and t-conorms. Fuzzy Sets and Systems, 142, 85–104.Google Scholar
Boguñá, M., Papadopoulos, F., & Krioukov, D. (2010). Sustaining the Internet with hyperbolic mapping. Nature communications, 1, 62.Google Scholar
Börner, K., Dall'Asta, L., Ke, W., & Vespignani, A. (2005). Studying the emerging global brain: Analyzing and visualizing the impact of co-authorship teams. Complexity, 10 (4), 57–67.Google Scholar
Bornholdt, S., & Schuster, H. G. (2003). Handbook of graphs and networks. Weinhenm: Wiley-VCH.Google Scholar
Brandes, U.,& Erlebach, T. (2005). Network analysis methodological foundations. Berlin Heidelberg: Springer.Google Scholar
Coifman, R. R., Lafon, S., Lee, A. B., Maggioni, M., Nadler, B., Warner, F., & Zucker, S. W. (2005). Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps. Proceedings of the National Academy of Sciences of the United States of America, 102 (21), 7426–7431.Google Scholar
Cornelis, C., De Kesel, P., & Kerre, E. E. (2004). Shortest paths in fuzzy weighted graphs. International Journal of Intelligent Systems, 19 (11), 1051–1068.Google Scholar
Day, W. H., & Edelsbrunner, H. (1984). Efficient algorithms for agglomerative hierarchical clustering methods. Journal of Classification, 1 (1), 7–24.Google Scholar
de Goes, F., Goldenstein, S., & Velho, L. (2008). A hierarchical segmentation of articulated bodies. In Proceedings of the Symposium on Geometry Processing, pp. 1349–1356, Aire-la-Ville, Switzerland, Switzerland. Eurographics Association.Google Scholar
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271.Google Scholar
Ding, C. H. Q., He, X., Peng, H., & Holbrook, S. R. (2006). Transitive closure and metric inequality of weighted graphs: detecting protein interaction modules using cliques. International Journal of Data Mining and Bioinformatics, 1 (2), 162–177.Google Scholar
Dombi, J. (1982). A general class of fuzzy operators, the demorgan class of fuzzy operators and fuzziness measures induced by fuzzy operators. Fuzzy Sets & Systems, 8, 149–163.Google Scholar
Dombi, J. (2013). On a certain class of aggregative operators. Information Sciences, 245, 313–328.Google Scholar
Dorogovtsev, S. N., & Mendes, J. (2003). Evolution of networks. New York: Oxford University Press.Google Scholar
Dubois, D., & Prade, H. (1980). Fuzzy sets and systems. New York: Academic Press.Google Scholar
Fronczak, A., & Fronczak, P. (2009). Biased random walks in complex networks: The role of local navigation rules. Physical Review E, 80 (1), 016107.Google Scholar
Galvin, F., & Shore, S. (1991). Distance functions and topologies. American Mathematical Monthly, 98, 620–623.Google Scholar
Ginsberg, J., Mohebbi, M. H., Patel, R. S., Brammer, L., Smolinski, M. S., & Brilliant, L. (2009). Detecting influenza epidemics using search engine query data. Nature, 457 (7232), 1012–1014.Google Scholar
Goh, K.-I., Kahng, B., & Kim, D. (2005). Nonlocal evolution of weighted scale-free networks. Phys Rev E Stat Nonlin Soft Matter Phys, 72, 017103.Google Scholar
Golbeck, J., Parsia, B., & Hendler, J. (2003). Trust networks on the semantic web. Lecture Notes in Computer Science, 2782, 238–249.Google Scholar
Gondran, M., & Minoux, M. (2007). Dioids and semirings: Links to fuzzy sets and other applications. Fuzzy Sets and Systems, 158 (12), 1273–1294.Google Scholar
Grefenstette, G. (1994). Explorations in automatic thesaurus discovery. New York: Kluwer Academic.Google Scholar
Han, S.-C., Gu, Y.-D., & Li, H.-X. (2007). An application of incline matrices in dynamic analysis of generalized fuzzy bidirectional associative memories. Fuzzy Sets and Systems, 158 (12), 1340–1347.Google Scholar
Han, S.-C. & Li, H.-X. (2004). Indices and periods of incline matrices. Linear Algebra and its Applications, 387, 143–165.Google Scholar
Hirschman, L., Yeh, A., Blaschke, C., & Valencia, A. (2005). Overview of biocreative: Critical assessment of information extraction for biology. BMC Bioinformatics, 6 (Suppl 1), S1.Google Scholar
Klamt, S., Haus, U., & Theis, F. (2009). Hypergraphs and cellular networks. PLoS Computational Biology, 5 (5), 1–6.Google Scholar
Klein, M. C. (1991). Fuzzy shortest paths. Fuzzy Sets and Systems, 39 (1), 27–41.Google Scholar
Klement, E., Mesiar, R., & Pap, E. (2004). Triangular norms. position paper ii: General constructions and parameterized families. Fuzzy Sets and Systems, 145 (3), 411–438.Google Scholar
Klement, E. P., Mesiar, R., & Pap, E. (2000). Triangular norms. Dordrecht, Netherlands: Kluwer Academic Publishers.Google Scholar
Klir, G., & Yuan, B. (1995). Fuzzy sets and fuzzy logic, theory and applications. Upper Saddle River, NJ: Prentice Hall PTR.Google Scholar
Kolchinsky, A., Abi-Haidar, A., Kaur, J., Hamed, A. A., & Rocha, L. M. (2010). Classification of protein-protein interaction full-text documents using text and citation network features. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 7 (3), 400–411.Google Scholar
Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., & Boguñá, M. (2010). Hyperbolic geometry of complex networks. Physical Review E, 82 (3), 036106.Google Scholar
Lafon, S., & Lee, A. (2006). Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning, and data set parameterization. IEEE Transactions on Pattern Analysis and Machine Intelligence, IEEE Transactions on, 28 (9), 1393–1403.Google Scholar
Markines, B., Stoilova, L., & Menczer, F. (2006). Social bookmarks for collaborative search and recommendation. In Bookmark Hierarchies an Collaborative Recommendation. pp. 1375–1380.Google Scholar
Menger, K. (1942). Statistical metrics. Proceedings of the National Academy of Sciences, 28 (12), 535–537.Google Scholar
Miyamoto, S. (1990). Fuzzy sets in information retrieval and cluster analysis. Dordrecht, Netherlands: Kluwer Academic Publishers.Google Scholar
Monge, P. R., & Contractor, N. S. (2003). Theories of communication networks. Oxford: Oxford University Press.Google Scholar
Mordeson, J., & Nair, P. (2000). Fuzzy graphs and fuzzy hypergraphs. Heidelberg: Physica-Verlag.Google Scholar
Nakamura, K., Iwai, S., & Sawaragi, T. (1982). Decision support using causation knowledge base. IEEE Transactions on Systems, Man and Cybernetics, IEEE Transactions on, 12 (6), 765–777.Google Scholar
Newman, M. E. (2001a). Scientific collaboration networks. ii. shortest paths, weighted networks, and centrality. Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 64 (1), 016132.Google Scholar
Newman, M. E. (2001b). The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences USA, 98 (2), 404–409.Google Scholar
Newman, M. E. J. (2004). Fast algorithm for detecting community structure in networks. Physical Review E, 69 (6), 066133.Google Scholar
Noh, J. D.,& Rieger, H. (2004). Random walks on complex networks. Physical Review Letters, 92 (11), 118701.Google Scholar
Nuutila, E. & Soisalon-Soininen, E. (1994). On finding the strongly connected components in a directed graph. Information Processing Letters, 49 (1), 9–14.Google Scholar
Oltvai, Z., & Barabasi, A. (2002). Systems biology. Life's complexity pyramid. Science, 298 (5594), 763–764.Google Scholar
Pang, C.-T. (2003). On the sequence of consecutive powers of fuzzy matrix with max-archimedean-t-norms. Fuzzy Sets & Systems, 138 (3), 643–656.Google Scholar
Pastor-Satorras, R., & Vespignani, A. (2004). Evolution and structure of the Internet a statistical physics approach. Cambridge, UK: Cambridge University Press.Google Scholar
Popescu, M., Keller, J., & Mitchell, J. (2006). Fuzzy measures on the gene ontology for gene product similarity. IEEE/ACM Transactions on Computational Biology and Bioinformatics, IEEE/ACM Transactions on, 3, 263–274.Google Scholar
Pujol, J. M., Sangüesa, R., & Delgado, J. (2002). Extracting reputation in multi agent systems by means of social network topology. In AAMAS '02: Proceedings of the 1st International Joint Conference on Autonomous Agents and Multiagent Systems, New York, NY, USA. ACM Press, pp. 467–474.Google Scholar
Rocha, L. M. (1999). Evidence sets: Modeling subjective categories. International Journal of General Systems, 27 (6):457–494.Google Scholar
Rocha, L. M. (2001). Combination of evidence in recommendation systems characterized by distance functions. In 2002 IEEE International Conference on Fuzzy Systems: FUZZ-IEEE'02; May 12–17 2002; Honolulu, HI, United States.Google Scholar
Rocha, L. M. (2002a). Proximity and semi-metric analysis of social networks. Technical report, Los Alamos National Laboratory: LAUR 02-6557.Google Scholar
Rocha, L. M. (2002b). Semi-metric behavior in document networks and its application to recommendation systems. In Loia, V. (Ed.), Soft computing agents: a new perspective for dynamic information systems, International Series Frontiers in Artificial Intelligence and Applications, Amsterdam, Netherlands: IOS Press, pp. 137–163.Google Scholar
Rocha, L. M. (2003). Automatic conversation driven by uncertainty reduction and combination of evidence for recommendation agents. In NATO Advanced Research Workshop on Systematic Organisation of Information in Fuzzy Systems; October 24–26, 2001; Vila Real, PORTUGAL. IOS Press.Google Scholar
Rocha, L. M. & Bollen, J. (2001). Biologically motivated distributed designs for adaptive knowledge management. In Cohen, I & Segel, L. (Eds.), Design Principles for the Immune System and other Distributed Autonomous Systems, Oxford: Oxford University Press, pp. 305–334.Google Scholar
Rocha, L., Simas, T., Rechtsteiner, A., DiGiacomo, M., & Luce, R. (2005). Mylibrary@lanl: Proximity and semi-metric networks for a collaborative and recommender web service. In I. Press (Ed.) Proceedings of the 2005 IEEE/WIC/ACM International Conference on Web Intelligence (WI'05), pp. 565–571.Google Scholar
Rubinov, M., & Sporns, O. (2010). Complex network measures of brain connectivity: Uses and interpretations. Neuroimage, 52 (3), 1059–69.Google Scholar
Serrano, M. A., Boguna, M., & Sagues, F. (2012). Uncovering the hidden geometry behind metabolic networks. Molecular BioSystems, 8 (3), 843–850.Google Scholar
Serrano, M. A., Krioukov, D. & Boguñá, M. (2008). Self-similarity of complex networks and hidden metric spaces. Physical Review Letters, 100 (7), 078701.Google Scholar
Shenoi, S., & Melton, A. (1989). Proximity relations in the fuzzy relational database model. Fuzzy Sets and Systems, 31 (3), 285–296.Google Scholar
Siek, J., Lee, L.-Q., & Lumsdaine, A. (2002). The boost graph library. Boston, MA: Addison-Wesley.Google Scholar
Simas, T., & Rocha, L. M. (2012). Semi-metric networks for recommender systems. In 2012 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology, Macau, pp. 175–179.Google Scholar
Stadler, B. M., Stadler, P. F., Wagner, G. P., & Fontana, W. (2001). The topology of the possible: Formal spaces underlying patterns of evolutionary change. Journal of Theoretical Biology, 213 (2), 241–274.Google Scholar
Stoilova, L., Holloway, T., Markines, B., Maguitman, A. G., & Menczer, F. (2005). Givealink: Mining a semantic network of bookmarks for web search and recommendation. In LinkKDD '05: Proceedings of the 3rd International Workshop on Link discovery, New York, NY, USA. ACM, pp. 66–73.Google Scholar
Strehl, A. (2002). Relationship-based Clustering and Cluster Ensembles for High-dimensional Data Mining. PhD thesis, Austin University of Texas.Google Scholar
Turney, P. D. (2001). Mining the Web for synonyms: PMI–IR versus LSA on TOEFL. Lecture Notes in Computer Science, Proceedings of the Twelfth European Conference on Machine Learning (ECML-2001). Freiburg, Germany, 491–502, NRC 44893.Google Scholar
Verspoor, K., Cohn, J., Joslyn, C., Mniszewski, S., Rechtsteiner, A., Rocha, L., & Simas, T. (2005). Protein annotation as term categorization in the gene ontology using word proximity networks. BMC Bioinformatics, pages 6 (Suppl 1), S20. doi:10.1186/1471-2105-6-S1-S20.Google Scholar
Wall, M. E., Rechtsteiner, A., & Rocha, L. M. (2003). Singular value decomposition and principal component analysis. In Berrar, D., Dubitzky, W., & Granzow, M., (Eds.) A practical approach to microarray data analysis, pp. 91–109. Norwell, MA: Kluwer.Google Scholar
Wang, W.-X., Wang, B.-H., Hu, B., Yan, G., & Ou, Q. (2005). General dynamics of topology and traffic on weighted technological networks. Physical Review Letters, 94 (18), 188702.Google Scholar
Wasserman, S., & Faust, K. (1994). Social networks analysis: Methods and applications. Cambridge: Cambridge University Press.Google Scholar
Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature(London), 393 (6684), 440–442.Google Scholar
Yan, G., Zhou, T., Wang, J., Fu, Z.-Q., & Wang, B.-H. (2005). Epidemic spread in weighted scale-free networks. Chinese Physics Letters, 22 (2), 510.Google Scholar
Ying, M. (1994). A logic for approximate reasoning. Journal of Symbolic Logic, 59 (3), 830–837.Google Scholar
Zadeh, L. (1965). Fuzzy sets and systems. In Fox, J. (Ed.), System theory, pp. 29–37. Brooklyn, NY: Elsevier.Google Scholar
Zadeh, L. (1999). Fuzzy logic and the calculi of fuzzy rules, fuzzy graphs, and fuzzy probabilities. Computers & Mathematics with Applications, 37 (11–12), 35.Google Scholar
Zwick, U. (2002). All pairs shortest paths using bridging sets retangular matrix multiplication. Journal of the ACM, 49 (3), 289–317.Google Scholar
Supplementary material: PDF

Simas and Rocha supplementary material S1

Simas and Rocha supplementary material S1

Download Simas and Rocha supplementary material S1(PDF)
PDF 599 KB