Common part of preference relations

• Autorzy: Levin, M. S.
• Języki publikacji: EN

Abstrakty

EN

The paper addresses a problem to build a common part for a set of preference relations (digraphs, posets) which are defined over the same set of vertices (e.g., alternatives). A special new contradiction is proposed for the vertices which are included into the common subgraph. A new problem formulation is: find the largest (by vertices and by arcs) common subgraph or its the ''best" approximation, while taking into account a contradiction. Thus the model is oriented to Pareto-effective solutions. The common subgraph can be considered as a structural measure for proximity of initial preference relations. The case of many initial digraphs allows various kinds of the aggregation for arc information. Our solving scheme is based on a combinatorial model (morphological clique problem). The following situations are described: (a) a general description for the two digraphs case and (b) the n digraph case. Numerical examples illustrate the problems and solving processes.

Słowa kluczowe

EN

common part; preference relations

• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2003
• Tom: Vol. 28, No. 4
• Strony: 223-246
• Opis fizyczny: Bibliogr. 87 poz.

Twórcy

autor

Levin, M. S.

• Ben-Gurion University, Beer Sheva, Israel,

Bibliografia

• [1] Akutsu T. and Halldorsson M.M., On the Approximation of Largest Common Subtrees and Largest Common Point Sets, Theor. Comp. Sci., 233, 1-2, 2000, 33-50.
• [2] Amir A. and Keselman D., Maximum Agreement Subtree of a Set of Evolutionary Trees - Metrics and Efficient Algorithms, SIAM J. on Comp., 26, 6, 1997, 1656-1669.
• [3] Baker B.S. and Giancarlo R., Sparse Dynamic Programming for Longest Common Subsequence from Fragments, J. of Algorithms, 42, 2, 2002, 231-254.
• [4] Balinska K.T., Brightwell G.R., and Quintas L.V., Graphs Whose Vertices are Graphs with Bounded Degree: Distance Problems. Res. Report LSE-CDAM-97-05, Centre for Disc. and Applicable Math., London School of Econ. & Polit. Sci., 1997.
• [5] Bar-Noy A. and Dolev D., Families of Consensus Algorithms, in: J.H. Reif (Ed.) VLSI Algorithms and Architectures, LNCS, 319, Springer, 1998, 380-390.
• [6] Barthelemy J.-P. and Guenoche A., Trees and Proximity Representation, Wiley, Chichester, 1991.
• [7] Berge C., Hypergraphs: Combinatorics of Finite Sets, North Holland, Amst., 1989.
• [8] Berman O. and Ashrafi N., Optimization Models for Reliability of Modular Software Systems, IEEE Trans. Soft. Eng., 19, 11, 1993, 1119-1123.
• [9] Bogart K.P., Preference Structures I: Distance between Transitive Preference Relations, J. Math. Soc., 3, 1973, 49-67.
• [10] Botafogo R.A., Rivlin E., and Shneiderman B., Structural Analysis of Hypertexts: Identifying Hierarchies and Useful Metrics, ACM Trans. Inform. Syst., 10, 2, 1992, 142-180.
• [11] Bunke H., On a Relation between Graph Edit Distance and Maximum Common Subgraph, Pattern Recogn. Lett., 18, 8, 1997, 689-694.
• [12] Bunke H. and Shearer K., A Graph Distance Metric Based on the Maximal Common Subgraph, Pattern Recogn. Lett., 19, 3-4, 1998, 255-259.
• [13] Chen S.-M., Interval-Valued Fuzzy Hypergraph and Fuzzy Partition, IEEE Trans. SMC - Part B, 27, 4, 1997, 725-732.
• [14] Chew L.P., Kedem K., Huttenlocher D.P., and Kleinberg J., Fast Detection of Geometric Substructure in Protein. J. of Comput. Biology, 6, 3-4, 1999, 313-325.
• [15] Cleary S., Restricted Rotation Distance between Binary Trees, Inform. Process. Lett., 84, 6, 2002, 333-338.
• [16] Cook W.D. and Kress M., Ordinal Information and Preference Structures: Decision Models and Applications, Prentice Hall, Englewood Cliffs, NJ, 1992.
• [17] Culik II, K. and Wood D., A Note on Some Tree Similarity Measures, Inform. Process. Lett., 15, 1, 1982, 39-42.
• [18] Dean P.M. (ed.), Molecular Similarity in Drug Design, Kluwer, Dordrecht, 1994.
• [19] Egenhofer M.J. and Shariff A.R.B.M., Metric Details for Natural-Language Spatial Relations, ACM Trans. Inform. Syst., 16, 4, 1998, 295-321.
• [20] Egghe L. and Michel C., Strong Similarity Measures for Ordered Sets of Documents in Information Retrieval, Inform. Proc. & Manag., 38, 6, 2002, 823-848.
• [21] El-Kwae E.A. and Kabuka M.R., Efficient Content-Based Indexing of Large Image Databases, ACM Trans. Inform. Syst., 18, 2, 2000, 171-219.
• [22] Farach M. and Thorup M., Sparse Dynamic Programming for Evolutionary Tree Comparison, SIAM J. on Computing, 26, 1, 1997, 210-230.
• [23] Finden C.R. and Gordon A.D., Obtaining Common Pruned Trees, J. of Classification, 2, 1985, 255-276.
• [24] Fishburn P.C., Utility Theory for Decision Making, Wiley, New York, 1970.
• [25] Garey M.R. and Johnson D.S., Computers and Intractability. The Guide to the Theory of NP-Completeness, W.H. Freeman: San Francisco, 1979.
• [26] Gordon A.D., Consensus of Supertrees: The Synthesis of Rooted Trees Containing Overlapping Sets of Labeled Leaves, J. of Classification, 3, 2, 1986, 335-348.
• [27] Gordon A.D., Constructing Dissimilarity Measures, J. of Classification, 7, 2, 1990, 257-269.
• [28] Gower J.C., Measures of Similarity, Dissimilarity, and Distance, in: Encyclopedia of Stat. Sci., 5, S. Kotz and N.L. Johnson (eds.), Wiley, New York, 1985, 397-405.
• [29] Gudivada V.N. and Raghavan V.V., Design and Evaluation of Algorithms for Image Retrieval by Spatial Similarity, ACM Trans. Inf. Syst., 13, 2, 1995, 115-144.
• [30] Hannenhalli S. and Pevzner P., Transforming Men into Mice, Technical Report CSE-95-012, Dept. of Comp. Sci. and Eng., Pennsylvania State Univ., 1995.
• [31] Herrera-Viedma E., Herrera F., and Chiclana F., A Consensus Model for Multiperson Decision Making With Different Preference Structures, IEEE Trans. SMC - Part A, 32, 3, 2002, 394-402.
• [32] Horaud R. and Skordas T., Stereo Correspondence through Feature Grouping and Maximal Cliques, IEEE Trans. PAMI, 11, 11, 1989, 1168-1180.
• [33] Huttenlocher D.P., Klanderman G.A., and Rucklidge W.J., Comparing Images Using the Hausdorff Distance, IEEE Trans. PAMI, 15, 9, 1993, 850-863.
• [34] Jiang X., Munger A., and Bunke H., On Median Graphs: Properties, Algorithms, and Applications, IEEE Trans. PAMI, 23, 10, 2001, 1144-1151.
• [35] Jolion J.-M., Feature Similarity, in: M.S. Lev (ed.) Visual Information Retrieval, Springer, London, 2001, 121-143.
• [36] Kacprzyk J., Nurmi H., and Fedrizzi M., (Eds.), Consensus Under Fuzziness, Kluwer, Boston, 1997.
• [37] Keeney R.L. and Raiffa H., Decisions with Multiple Objectives: Preferences and Value Tradeoffs, Wiley, New York, 1976.
• [38] Kemeny J.G., Mathematical Models in the Social Sciences, MIT Press, Cambridge, Mass., 1972.
• [39] Knuth D.E. and Raghunathan A., The Problem of Compatible Representatives, SIAM J. on Disc. Math., 5, 3, 1992, 422-427.
• [40] Kupeev K.Y. and Wolfson H.J., A New Method of Estimating Shape Similarity, Pattern Recogn. Lett., 17, 1996, 873-887.
• [41] Kvasnicka V. and Pospichal J., Maximal Common Subgraphs of Molecular Graphs, Reports Molecular Theory, 1, 1990, 99-106.
• [42] Levin M.Sh., Hierarchical Morphological Multicriteria Design of Decomposable Systems, Concurrent Engineering: Res. and Appl., 4, 2, 1996, 111-117.
• [43] Levin M.Sh., Combinatorial Engineering of Decomposable Systems, Kluwer, Dordrecht, 1998.
• [44] Levin M.Sh., Towards Common Part of Preference Relations. Presentation, The 5th Int. Meeting of The Society for Social Choice and Welfare, Alicante, 2000.
• [45] Levin M.Sh., System Synthesis with Morphological Clique Problem: Fusion of Subsystem Evaluation Decisions, Information Fusion, 2, 3, 2001, 225-237.
• [46] Levin M.Sh. and Rival I., A Procedure: Common Part of Two Digraphs, Proc. Int. Conf. on Control Problems, 2, Moscow, 1999, 53-57.
• [47] Levinson R., Pattern Associativity and the Retrieval of Semantic Networks, Comput. Math. Appl., 23, 1992, 573-600.
• [48] Li S.-H. and Danzig P., Boolean Similarity Measures for Resource Discovery, IEEE Trans. Knowl. Data Eng., 9, 6, 1997, 863-876.
• [49] Makinen E., On the Rotation Distance of Binary Trees, Inform. Process. Lett., 26, 5, 1988, 271-272.
• [50] Margush T., Distance Between Trees, Discr. Appl. Math., 4, 1982, 281-290.
• [51] Martello S. and Toth P., Knapsack Problem: Algorithms and Computer Implementation, Wiley, New York, 1990.
• [52] McGregor J.J., Backtracking Search Algorithms and the Maximum Common Subgraph Problem, Software - Practice and Experience, 12, 1982, 23-34.
• [53] Michel C., Ordered Similarity Measures Taking into Account the Rank of Documents, Inform. Proc. & Manag., 37, 4, 2000, 603-622.
• [54] Mirkin B.G., Mathematical Classification and Clustering, Kluwer, Boston, 1996.
• [55] Mirkin B.G. and Chernyi L.B., On Measurement of Distance Between Partition of a Finite Set of Units, Automation and Remote Control, 31, 1970, 786-792.
• [56] Mirkin B.G. and Roberts F.S., Consensus Functions and Patterns in Molecular Sequences. Bulletin of Mathematical Biology, 55, 1993, 695-713.
• [57] Mirkin B.G., Muchnik I., and Smith T., A Biologycally Consistent Model for Comparing Molecular Phylogenies, J. of Molecular Biology, 2, 4, 1995, 493-507.
• [58] Montello D., The Measurement of Cognitive Distances: Methods and Construct Validity, J. of Environmental Psychology, 11, 2, 1991, 101-122.
• [59] Myaeng S.H. and Lopez-Lopez A., Conceptual Graph Matching: a Flexible Algorithm and Experiments, J. of Exper. and Theor. Artif. Intell., 4, 1992, 107-126.
• [60] Pallo J., An Efficient Upper Bound of the Rotation Distance of Binary Trees, Inform. Process. Lett., 73, 3-4, 2000, 87-92.
• [61] Pelillo M., Matching Free Trees, Maximal Cliques, and Monotone Game Dynamics, IEEE Trans. PAMI, 24, 2002, 1535-1541.
• [62] Pevzner P.A., Computational Biology: An Algorithmic Approach, MIT Press, Cambridge, 2000.
• [63] Poole J. and Campbell J.A., A Novel Algorithm for Matching Conceptual and Related Graphs, in: Proc. of the Third Int. Conf. on Conceptual Structures, LNCS, 954, Springer, 1995, 293-307.
• [64] Rappoport A.M., Measurement of Distance Between Weighted Graphs of Expert Judgment, Multicriteria Choice for Solving of Ill-structured Problems, 5, Inst, for System Analysis, Moscow, 1978, 97-108 (in Russian).
• [65] Raymond J.W., Gardiner E.J., and Willett P., Heuristic for Rapid Similarity Searching of Chemical Graphs Using a Maximum Common Edge Subgraph Algorithm, J. of Chem. Inf. Comput. Sci., 42, 2002, 305-316.
• [66] Raymond J.W., Gardiner E.J., and Willett P., RASCAL: Calculation of Graph Similarity using Maximal Common Edge Subgraph, The Computer J., 45, 6, 2002, 631-644.
• [67] Roberts F.R., Discrete Mathematical Models with Applications to Social, Biological and Environmental Problems, Prentice Hall, Englewood Cliffs, NJ, 1976.
• [68] Robinson D.F. and Foulds L.R., Comparison of Phylogenetic Trees, Math. Biosciences, 53, 1/2, 1981, 131-147.
• [69] Roy B., The Outranking Approach and Foundations of ELECTRE Methods, in: C.A. Bana e Costa (ed.), Readings in Multi-Criteria Decision Aid, Springer, Berlin, 1990, 155-183.
• [70] Saaty T.L., The Analytic Hierarchy Process, MacGraw-Hill, New York, 1988.
• [71] Shapiro L.G. and Haralik R.M., Structural Description and Inexact Matching, IEEE Trans. PAMI, 3, 1981, 504-519.
• [72] Shearer K., Bunke H., and Venkatesh S., Video Indexing and Similarity Retrieval by Largest Common Subraph Detection Using Decision Trees, Pattern Recogn., 34, 5, 2001, 1075-1091.
• [73] Smith T.F. and Waterman M.S., Identification of Common Molecular Subsequencies, J. of Molecular Biology, 147, 1981, 195-197.
• [74] Steel M. and Warnow T., Kaikoura Tree Theorem: Computing the Maximum Agreement Subtree, Inform. Process. Lett., 48, 2, 1993, 77-82.
• [75] Tai K.-C., The Tree-to-Tree Correction Problem, J. of the ACM, 26, 3, 1979, 422-433.
• [76] Tanaka E., Takemasa K., and Masuda S., A Distance Measure for Molecular Structures and its Computing Method, Pattern Recogn. Lett., 19, 3-4, 1998, 373-381.
• [77] Timkovsky V.G., Complexity of Common Subsequence and Supersequence Problems and Related Problems, Cybernetics, 25, 1990, 565-580.
• [78] Tversky A., Features of Similarity, Psychological Review, 84, 4, 1977, 327-352.
• [79] Vassilakopoulos M. and Manolopoulos Y., Analytical Comparison of Two Spatial Data Structures, Information Systems, 19, 7, 1994, 569-582.
• [80] Wagner R.A. and Fischer M.J., The String-to-String Correction Problem, J. of the ACM, 23, 1, 1974, 31-42.
• [81] Wallis W.D., Shoubridge P., Kraetz M., and Ray D., Graph Distances Using Graph Union, Pattern Recogn. Lett., 22, 6-7, 2001, 701-704.
• [82] Wang J. and Malakooti B., A Feedforward Neural Network for Multiple Criteria Decision Making, Comput. & Oper. Res., 19, 2, 1992, 151-167.
• [83] Wang Y. and Ishii N., A Method of Similarity Metrics for Structured Representations, Expert Syst. with Appl., 12, 1, 1997, 89-100.
• [84] Werman M., Peleg S., and Rosenfeld A., A Distance Metric for Multidimensional Histograms, Comput. Vision, Graph., Image Processing, 32, 1985, 328-336.
• [85] Willet P., Matching of Chemical and Biological Structures Using Subgraphs and Maximal Common Subgraphs Isomorphism Algorithms, IMA Vol. Math. Appl., 108, 1999, 11-38.
• [86] Zhang K., Wang J.T.L., and Shasha D., On the Editing Distance between Undirected Acyclic Graphs, Int. J. Foundations of Comp. Sci., 7, 1, 1996, 43-57.
• [87] Zwicky F., Discovery Invention, Research Through the Morphological Approach, McMillan, New York, 1969.