Graph ambiguity. (English) Zbl 1284.68538
Summary: In this paper, we propose a rigorous way to define the concept of ambiguity in the domain of graphs. In past studies, the classical definition of ambiguity has been derived starting from fuzzy set and fuzzy information theories. Our aim is to show that also in the domain of the graphs it is possible to derive a formulation able to capture the same semantic and mathematical concept. To strengthen the theoretical results, we discuss the application of the graph ambiguity concept to the graph classification setting, conceiving a new kind of inexact graph matching procedure. The results prove that the graph ambiguity concept is a characterizing and discriminative property of graphs.
MSC:
| 68T30 | Knowledge representation |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68T05 | Learning and adaptive systems in artificial intelligence |
Keywords:
information measures; fuzzy sets; fuzzy clustering; graph matching; graph representation; graph miningReferences:
| [1] | Aggarwal, C.; Wang, H., Managing and Mining Graph Data, Advances in Database Systems (2010), Springer · Zbl 1185.68458 |
| [2] | Aizerman, A.; Braverman, E. M.; Rozoner, L. I., Theoretical foundations of the potential function method in pattern recognition learning, Autom. Remote Control, 25, 821-837 (1964) · Zbl 0151.24701 |
| [4] | Alsina, C.; Schweizer, B.; Frank, M., Associative FunctionsTriangular Norms and Copulas (2006), World Scientific · Zbl 1100.39023 |
| [7] | Bhandari, D.; Pal, N. R., Some new information measures for fuzzy sets, Inf. Sci., 67, 209-228 (1993) · Zbl 0763.94030 |
| [8] | Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D., Complex networksstructure and dynamics, Phys. Rep., 424, 175-308 (2006) · Zbl 1371.82002 |
| [9] | Bollobás, B., Modern Graph Theory, Graduate Texts in Mathematics (1998), Springer · Zbl 0902.05016 |
| [10] | Borg, I.; Groenen, P., Modern Multidimensional ScalingTheory and Applications, Springer Series in Statistics (2005), Springer · Zbl 1085.62079 |
| [11] | Borgwardt, K. M.; Ong, C. S.; Schönauer, S.; Vishwanathan, S. V.N.; Smola, A. J.; Kriegel, H. P., Protein function prediction via graph kernels, Bioinformatics, 21, 47-56 (2005) |
| [13] | Brandes, U., A faster algorithm for betweenness centrality, J. Math. Sociol., 25, 163-177 (2001) · Zbl 1051.91088 |
| [14] | Brandes, U.; Delling, D.; Gaertler, M.; Görke, R.; Hoefer, M.; Nikoloski, Z.; Wagner, D., On finding graph clusterings with maximum modularity, (Brandstädt, A.; Kratsch, D.; Müller, H., Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 4769 (2007), Springer: Springer Berlin, Heidelberg), 121-132 · Zbl 1141.68519 |
| [16] | Brandes, U.; Gaertler, M.; Wagner, D., Engineering graph clusteringmodels and experimental evaluation, J. Exp. Algorithmics, 12, 1-26 (2008) · Zbl 1143.05311 |
| [17] | Brin, S.; Page, L., The anatomy of a large-scale hypertextual Web search engine, Comput. Networks ISDN Syst., 30, 107-117 (1998) |
| [19] | Chung, F., Spectral Graph Theory (1994), AMS |
| [20] | Chung, F., Laplacians and the Cheeger inequality for directed graphs, Ann. Combin., 9, 1-19 (2005) · Zbl 1059.05070 |
| [21] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT Press · Zbl 1047.68161 |
| [23] | Diestel, R., Graph Theory, Graduate Texts in Mathematics (2006), Springer |
| [26] | Fan, J. L.; Ma, Y. L., Some new fuzzy entropy formulas, Fuzzy Sets Syst., 128, 277-284 (2002) · Zbl 1018.94003 |
| [28] | Gao, X.; Xiao, B.; Tao, D.; Li, X., A survey of graph edit distance, Pattern Anal. Appl., 13, 113-129 (2010) · Zbl 1422.68211 |
| [29] | Guimera, R.; Amaral, L. A.N., Functional cartography of complex metabolic networks, Nature, 433, 895 (2005) |
| [30] | Hájek, P., Metamathematics of Fuzzy Logic, Trends in Logic Series (2001), Kluwer |
| [31] | Hand, D.; Mannila, H.; Smyth, P., Principles of Data Mining, Adaptive Computation and Machine Learning (2001), MIT Press |
| [33] | Havlin, S., Complex Networks (2010), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1196.05092 |
| [35] | Hooda, D., On generalized measures of fuzzy entropy, Math. Slovaca, 54, 315-325 (2004) · Zbl 1086.94047 |
| [36] | Jain, B. J.; Obermayer, K., Structure spaces, J. Mach. Learn. Res., 10, 2667-2714 (2009) · Zbl 1235.68159 |
| [38] | Jolliffe, I., Principal Component Analysis, Springer Series in Statistics (2002), Springer · Zbl 1011.62064 |
| [39] | Kannan, R.; Vempala, S.; Vetta, A., On clusteringsgood, bad, and spectral, J. ACM (JACM), 51, 497-515 (2004) · Zbl 1192.05160 |
| [42] | Kaufmann, A., Introduction to the Theory of Fuzzy Subsets, vol. 2 (1975), Academic Press · Zbl 0332.02063 |
| [43] | Kleinberg, J. M., Authoritative sources in a hyperlinked environment, J. ACM, 46, 604-632 (1999) · Zbl 1065.68660 |
| [44] | Klir, G., Uncertainty and InformationFoundations of Generalized Information Theory (2006), Wiley-Interscience · Zbl 1280.94004 |
| [45] | Kosko, B., Fuzzy entropy and conditioning, Inf. Sci., 40, 165-174 (1986) · Zbl 0623.94005 |
| [46] | Kosko, B., Addition as fuzzy mutual entropy, Inf. Sci., 73, 273-284 (1993) · Zbl 0782.94005 |
| [47] | Kullback, S., Information Theory and Statistics, Dover Books on Mathematics (1997), Dover Publications · Zbl 0897.62003 |
| [48] | Kullback, S.; Leibler, R. A., On information and sufficiency, Ann. Math. Stat., 22, 79-86 (1951) · Zbl 0042.38403 |
| [51] | Livi, L.; Rizzi, A., The graph matching problem, Pattern Anal. Appl. (2012), http://dx.doi.org/10.1007/s10044-012-0284-8 · Zbl 1284.68470 |
| [52] | Luca, A. D.; Termini, S., A definition of a nonprobabilistic entropy in the setting of fuzzy sets theory, Inf. Control, 20, 301-312 (1972) · Zbl 0239.94028 |
| [53] | Ma, H. W.; Zhao, X. M.; Yuan, Y. J.; Zeng, A. P., Decomposition of metabolic network into functional modules based on the global connectivity structure of reaction graph, Bioinformatics, 20, 1870-1876 (2004) |
| [54] | Martins, A. F.T.; Smith, N. A.; Xing, E. P.; Aguiar, P. M.Q.; Figueiredo, M. A.T., Nonextensive information theoretic kernels on measures, J. Mach. Learn. Res., 10, 935-975 (2009) · Zbl 1235.68174 |
| [55] | Neuhaus, M.; Bunke, H., Bridging the Gap between Graph Edit Distance and Kernel Machines, Series in Machine Perception and Artificial Intelligence (2007), World Scientific · Zbl 1140.68473 |
| [56] | Pal, N. R.; Pal, S. K., Higher order fuzzy entropy and hybrid entropy of a set, Inf. Sci., 61, 211-231 (1992) · Zbl 0746.94007 |
| [57] | Pe¸kalska, E.; Duin, R., The Dissimilarity Representation for Pattern RecognitionFoundations and Applications, Series in Machine Perception and Artificial Intelligence (2005), World Scientific · Zbl 1095.68105 |
| [58] | Pedrycz, W.; Gomide, F., An Introduction to Fuzzy SetsAnalysis and Design, Complex Adaptive Systems (1998), MIT Press · Zbl 0938.03078 |
| [59] | Príncipe, J. C., Information Theoretic LearningRenyi’s Entropy and Kernel Perspectives, Information Science and Statistics (2010), Springer · Zbl 1206.94003 |
| [60] | Rademacher, H., On the partition function \(p(n)\), Proc. London Math. Soc., s2-43, 241-254 (1938) · JFM 63.0140.02 |
| [62] | Riesen, K.; Bunke, H., Graph Classification and Clustering Based on Vector Space Embedding, Series in Machine Perception and Artificial Intelligence (2010), World Scientific Pub Co. Inc. · Zbl 1231.68233 |
| [64] | Rota, G. C., The number of partitions of a set, Am. Math. Mon., 71, 498-504 (1964) · Zbl 0121.01803 |
| [65] | Schenker, A., Graph-Theoretic Techniques for Web Content Mining, Series in Machine Perception and Artificial Intelligence (2005), World Scientific · Zbl 1077.68007 |
| [66] | Schölkopf, B.; Smola, A., Learning with KernelsSupport Vector Machines, Regularization, Optimization, and Beyond, Adaptive Computation and Machine Learning (2002), MIT Press |
| [67] | Shang, X. G.; Jiang, W. S., A note on fuzzy information measures, Pattern Recognition Lett., 18, 425-432 (1997) |
| [68] | Shannon, C. E., A Mathematical Theory of Communication (1948), CSLI Publications · Zbl 1154.94303 |
| [69] | Shannon, C. E.; Weaver, W., A Mathematical Theory of Communication (1963), University of Illinois Press: University of Illinois Press Champaign, IL, USA · Zbl 0126.35701 |
| [70] | Sharp, H., Cardinality of finite topologies, J. Combin. Theory, 5, 82-86 (1968) · Zbl 0159.52202 |
| [71] | Shawe-Taylor, J.; Cristianini, N., Kernel Methods for Pattern Analysis (2004), Cambridge University Press |
| [72] | Sipser, M., Introduction to the Theory of Computation (2006), PWS Pub.: PWS Pub. Boston · Zbl 1191.68311 |
| [73] | Stephenson, K.; Zelen, M., Rethinking centralitymethods and examples, Soc. Networks, 11, 1-37 (1989) |
| [74] | Vishwanathan, S. V.N.; Borgwardt, K. M.; Kondor, R. I.; Schraudolph, N. N., Graph kernels, J. Mach. Learn. Res., 11, 1201-1242 (2010) · Zbl 1242.05112 |
| [75] | Wasserman, S.; Faust, K., Social Network AnalysisMethods and Applications (1994), Cambridge University Press |
| [77] | Xiao, B.; Gao, X.; Tao, D.; Li, X., HMM-based graph edit distance for image indexing, Int. J. Imaging Syst. Technol., 18, 209-218 (2008) |
| [78] | Yager, R. R., On measures of fuzziness and fuzzy complements, Int. J. General Syst., 5, 221-229 (1979) · Zbl 0429.04007 |
| [79] | You, C.; Wen, M., The entropy of fuzzy vectors, Comput. Math. Appl., 56, 1626-1633 (2008) · Zbl 1155.94358 |
| [80] | Zadeh, L., Probability measures of Fuzzy events, J. Math. Anal. Appl., 23, 421-427 (1968) · Zbl 0174.49002 |
| [81] | Zadeh, L. A., Fuzzy sets, Inf. Control, 8, 338-353 (1965) · Zbl 0139.24606 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
