Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and Applications to Large Graphs and Networks Modular

28/08/2013
OAI : oai:www.see.asso.fr:2552:4900
DOI :

Résumé

Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and Applications to Large Graphs and Networks Modular

Média

Voir la vidéo

Métriques

103
10
559.72 Ko
 application/pdf
bitcache://d3bb62bfb953e01067b6ba36d89272ec90249d52

Licence

Creative Commons Aucune (Tous droits réservés)

Sponsors

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors financier

logo_gdr-mia.png
logo_inria.png
image010.png
logothales.jpg

Sponsors logistique

logo-minesparistech.jpg
logo-universite-paris-sud.jpg
logo_supelec.png
Séminaire Léon Brillouin Logo
logo_cnrs_2.jpg
logo_ircam.png
logo_imb.png
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/2552/4900</identifier><creators><creator><creatorName>Jean-François Marcotorchino</creatorName></creator></creators><titles>
            <title>Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and Applications to Large Graphs and Networks Modular</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2013</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Tue 17 Sep 2013</date>
	    <date dateType="Updated">Sun 25 Dec 2016</date>
            <date dateType="Submitted">Fri 20 Jul 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">d3bb62bfb953e01067b6ba36d89272ec90249d52</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>25051</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and Applications to Large Graphs and Networks Modularity Jean-Franc¸ois Marcotorchino Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6 August 2013 Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 1 / 29 Outline 1 Goal of the Presentation 2 The optimal transport problem: Monge and Monge-Kantorovich Problems 3 Extensions and variants of the MKP problem 4 Monge and Anti-Monge matrices and some related structural properties 5 Duality related to ”Independence” and ”Indetermination” structures 6 Relational Analysis Approach 7 A new Graph modularization criterion Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 2 / 29 Goal of the Presentation Plan 1 Goal of the Presentation 2 The optimal transport problem: Monge and Monge-Kantorovich Problems 3 Extensions and variants of the MKP problem 4 Monge and Anti-Monge matrices and some related structural properties 5 Duality related to ”Independence” and ”Indetermination” structures 6 Relational Analysis Approach 7 A new Graph modularization criterion Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 3 / 29 Goal of the Presentation Goal of the Presentation Exhibiting a Relationship between Monge & Condorcet (1781-1785) 1 Using the Optimal Transport Theory, based on G. Monge (1781) and L. Kantorovitch MK Problem, for defining two alternatives for measuring ”correlation” within ”stressed contingency structures” according to M. Frechet’s first attempt of 1951. 2 Introducing two extended variants of the MKP Problem concerned with Spatial interaction Models: The ”Alan Wilson’s Entropy Model” and the Minimal Trade Model. 3 Deriving and Justifying from those models two ”dual structures” of correlation measures: Deviation from Independance (Mutual Information Index), Deviation from Indetermination (Indetermination Index). Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 4 / 29 Goal of the Presentation Goal of the Presentation 1 Justifying this duality through the so called Monge’s Conditions. 2 Translating those specific situations into very differentiate but usual indexes (the Tchuprow - χ2: and the Janson-Vegelius’s Index). 3 Explaining ”Deviation from Indetermination” by its filiation with the ”Relational Analysis scheme” of A. de Condorcet. 4 Applying this principle to ”Graphs Modularization Criteria”. Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 5 / 29 The optimal transport problem: Monge and Monge-Kantorovich Problems Plan 1 Goal of the Presentation 2 The optimal transport problem: Monge and Monge-Kantorovich Problems 3 Extensions and variants of the MKP problem 4 Monge and Anti-Monge matrices and some related structural properties 5 Duality related to ”Independence” and ”Indetermination” structures 6 Relational Analysis Approach 7 A new Graph modularization criterion Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 6 / 29 The optimal transport problem: Monge and Monge-Kantorovich Problems The Monge-Kantorovich Problem The Monge-Kantorovich Problem: P[π∗ ] = inf π∈Π(µ,ν) X×Y c(x, y)dπ(x, y) (1) The linear Monge-Kantorovich problem has a dual formulation: D[ϕ, ψ] = sup (ϕ,ψ) { X ϕdµ+ Y ψdν : c(x, y) ≥ ϕ(x)+ψ(y) on X ×Y } (2) Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 7 / 29 The optimal transport problem: Monge and Monge-Kantorovich Problems The Monge-Kantorovich Duality Theorem (Kantorovich duality) If there exists π∗ ∈ Π(µ, ν) and an admissible pair (ϕ∗, ψ∗) ∈ £ such that: X×Y c(x, y)dπ∗ (x, y) = X ϕ∗ (x)dµ(x) + Y ψ∗ (y)dν(y) then π∗ is an Optimal Transport Plan and the pair (ϕ∗, ψ∗) solves the problem (2). So there is no gap between the values: inf π P[π] = sup (ϕ,ψ) D[ϕ, ψ] Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 8 / 29 Extensions and variants of the MKP problem Plan 1 Goal of the Presentation 2 The optimal transport problem: Monge and Monge-Kantorovich Problems 3 Extensions and variants of the MKP problem 4 Monge and Anti-Monge matrices and some related structural properties 5 Duality related to ”Independence” and ”Indetermination” structures 6 Relational Analysis Approach 7 A new Graph modularization criterion Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 9 / 29 Extensions and variants of the MKP problem The discrete version of the MKP problem min π p u=1 q v=1 c(u, v)πuv (3) subject to: q v=1 πuv = µu ∀u ∈ {1, 2, ..., p} (4) p u=1 πuv = νv ∀v ∈ {1, 2, ..., q} (5) p u=1 q v=1 πuv = 1 (6) πuv ≥ 0 ∀u ∈ {1, ..., p}; v ∈ {1, ..., q} (7) Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 10 / 29 Extensions and variants of the MKP problem Variants of the MKP problem The Alan Wilson’s Entropy Model: Objective function Subject to Optimal solution max π − p u=1 q v=1 πuv ln πuv Contraints (4),(5) and (7) π∗ uv = µuνv∀(u, v) n∗ uv = nu.n.v N The Minimal Trade Model: Objective function Subject to Optimal solution min π p u=1 q v=1 πuv − 1 pq 2 Contraints (4),(5) and (7) π∗ uv = µu q + νv p − 1 pq n∗ uv = nu. q + n.v p − N pq Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 11 / 29 Extensions and variants of the MKP problem The Continuous version of the Minimal Trade Problem The optimal solution of the Continuous version of the Minimal Trade Problem, obtained by considering the Kantorovich duality (2), is given by: π∗ (x, y) = f(x) B + g(y) A − 1 AB ∀ (x, y) ∈ [a, b] × [c, d] where π : [a, b] × [c, d] −→ [0, 1] is defined on the product of two closed intervals of the cartesian plan; A = (b − a) and B = (d − c) are the respective lengths of those intervals; µ and ν (the marginals of π) have densities f and g respectively. Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 12 / 29 Monge and Anti-Monge matrices and some related structural properties Plan 1 Goal of the Presentation 2 The optimal transport problem: Monge and Monge-Kantorovich Problems 3 Extensions and variants of the MKP problem 4 Monge and Anti-Monge matrices and some related structural properties 5 Duality related to ”Independence” and ”Indetermination” structures 6 Relational Analysis Approach 7 A new Graph modularization criterion Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 13 / 29 Monge and Anti-Monge matrices and some related structural properties The Monge and anti-Monge Matrices Definition A p × q real matrix {cuv} is called a Monge matrix, if C satisfies the so called Monge’s property: cuv + cu v ≤ cuv + cu v ∀ 1 ≤ u < u ≤ p, 1 ≤ v < v ≤ q (8) Reciprocally, an ”Inverse Monge Matrix” (or Anti Monge matrix) C satisfies the following inequality: cuv + cu v ≥ cuv + cu v ∀ 1 ≤ u < u ≤ p, 1 ≤ v < v ≤ q (9) In case both inequalities (8) and (9) hold: cuv + cu v = cuv + cu v ∀ 1 ≤ u < u ≤ p, 1 ≤ v < v ≤ q (10) Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 14 / 29 Monge and Anti-Monge matrices and some related structural properties The Monge and anti-Monge Matrices Theorem Let {πuv} be a p × q real nonnegative frequency Matrix, then the following properties hold and are equivalent: i) If {πuv} is a Monge and Anti-Monge Matrix then: πuv + πu v = πuv + πu v ∀ 1 ≤ u < u ≤ p, 1 ≤ v < v ≤ q ii) πuv = µu q + νv p − 1 pq is a minimizer of the Minimal Trade Model. iii) All the sub tables {u, v, u , v } of size 2 × 2 with 1 ≤ u < u ≤ p, 1 ≤ v < v ≤ q have the sum of their diagonals equal to the sum of their anti-diagonals. Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 15 / 29 Monge and Anti-Monge matrices and some related structural properties The Log-Monge and Log-Anti-Monge Matrices Definition A p × q positive real matrix {cuv} is called a Log Monge matrix, if C satisfies the Log-Monge’s property: ln cuv+ln cu v ≤ ln cuv +ln cu v ∀ 1 ≤ u < u ≤ p, 1 ≤ v < v ≤ q (11) Reciprocally, an ”Inverse Log-Monge Matrix” (or Log-Anti-Monge matrix) C satisfies the following inequality: ln cuv+ln cu v ≥ ln cuv +ln cu v ∀ 1 ≤ u < u ≤ p, 1 ≤ v < v ≤ q (12) In case both inequalities (11) and (12) hold: ln cuv+ln cu v = ln cuv +ln cu v ∀ 1 ≤ u < u ≤ p, 1 ≤ v < v ≤ q (13) Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 16 / 29 Monge and Anti-Monge matrices and some related structural properties The Log-Monge and Log-Anti-Monge Matrices Theorem Let {πuv} be a p × q real positive frequency Matrix, then the following properties hold and are equivalent: i) If {πuv} is a Log-Monge and Log-Anti-Monge Matrix then: ln πuv + ln πu v = ln πuv + ln πu v ∀ 1 ≤ u < u ≤ p, 1 ≤ v < v ≤ q ii) πuv = µuνv ∀ 1 ≤ u < u ≤ p, 1 ≤ v < v ≤ q is a minimizer of the Alan Wilson’s Program of Spatial Interaction System based upon Entropy Model, with fixed Margins. iii) All the sub tables {u, v, u , v } of size 2 × 2 with 1 ≤ u < u ≤ p, 1 ≤ v < v ≤ q have the product of their diagonal terms equal to the product of their anti-diagonals terms. Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 17 / 29 Monge and Anti-Monge matrices and some related structural properties A contingency table X\Y 1 . . . v . . . q Total 1 n11 . . . n1v . . . n1q n1. ... ... ... ... ... u nu1 . . . nuv . . . nuq nu. ... ... ... ... ... p np1 . . . npv . . . npq np. Total n.1 . . . n.v . . . n.q n.. where: nuv = Nπuv : quantity of mass transported from u ∈ X to v ∈ Y . nu. = Nπu.: total mass located originaly at u. n.v = Nπ.v: total mass transported to v. n.. = N Total exchange mass. Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 18 / 29 Monge and Anti-Monge matrices and some related structural properties Example of applications of Monge’s conditions on two Contingency Tables subject to the same marginals Indetermination structure: A + B = C + D Independance Structure: AB = CD Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 19 / 29 Duality related to ”Independence” and ”Indetermination” structures Plan 1 Goal of the Presentation 2 The optimal transport problem: Monge and Monge-Kantorovich Problems 3 Extensions and variants of the MKP problem 4 Monge and Anti-Monge matrices and some related structural properties 5 Duality related to ”Independence” and ”Indetermination” structures 6 Relational Analysis Approach 7 A new Graph modularization criterion Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 20 / 29 Duality related to ”Independence” and ”Indetermination” structures The Mutual Information index (MI) and the The Deviation to indetermination Index (IND) The Mutual Information index (MI) ρMI: ρMI = SX + SY − S(X,Y ) where S(X,Y ) = − p u=1 q v=1 πuv ln πuv; SX = − p u=1 µu ln µu and SY = − q v=1 νv ln νv. The Deviation to indetermination Index (IND) ρIND: ρIND(X, Y ) = K(X,Y ) − KX − KY where K(X,Y ) = pq p u=1 q v=1 πuv − 1 pq 2 ; K(X) = p p u=1 µu − 1 p 2 and K(Y ) = q q v=1 νv − 1 q 2 . Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 21 / 29 Duality related to ”Independence” and ”Indetermination” structures Duality between independence and indetermination structures ∀X, Y |X ∼ µ , Y ∼ ν , (X, Y ) ∼ π The Independence case The Indetermination case S(X,Y ) ≤ SX + SY K(X,Y ) ≥ KX + KY with equality in case of inde- pendence with equality in case of indetermination ρMI(X, Y ) = SX +SY −S(X,Y ) = p u=1 q v=1 πuv ln πuv µuνv ρIND(X, Y ) = K(X,Y ) − KX − KY = pq p u=1 q v=1 πuv − µu q + νv p + 1 pq 2 Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 22 / 29 Duality related to ”Independence” and ”Indetermination” structures Translation of the duality between Independance and Indetermination into Contingency Correlation Measures Mutual Information Index behaves as the χ2 does in the Neibourhood of Independance: ρMI(X, Y ) ∼= p u=1 q v=1 (πuv − µuνv)2 µuνv = 1 n.. Fχ2 [π] The Janson-Vegelius index is fully derived from the Indetermination index ρIND(X, Y ): JV (X, Y ) = pq p u=1 q v=1 π2 uv − p p u=1 µ2 u. − q q v=1 ν2 .v + 1 p(p − 2) p u=1 µ2 u. + 1 q(q − 2) q v=1 ν2 .v + 1 ∀(X, Y ) Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 23 / 29 Relational Analysis Approach Plan 1 Goal of the Presentation 2 The optimal transport problem: Monge and Monge-Kantorovich Problems 3 Extensions and variants of the MKP problem 4 Monge and Anti-Monge matrices and some related structural properties 5 Duality related to ”Independence” and ”Indetermination” structures 6 Relational Analysis Approach 7 A new Graph modularization criterion Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 24 / 29 Relational Analysis Approach Relational Analysis Approach Principle: representing relations between objects by binary coding. A partition is nothing but an equivalence relation on the set of objects, which is represented by a relational N × N matrix X, whose entries are defined as follows: xij = 1 if i and j belong to the same cluster. 0 otherwise. (14) As X is an equivalence Relation, it must be Reflexive, Symmetric and Transitive, those properties can be turned into linear constraints on the general terms of the relational matrix X. ¯xij = 1 − xij ∀(i, j) is the inverse relation of X. Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 25 / 29 Relational Analysis Approach The Relational Transfer Principle p u=1 q v=1 π2 uv = 1 N2 N i=1 N j=1 xijyij ; p u=1 µ2 u. = 1 N2 N i=1 N j=1 xij; q v=1 ν2 .v = 1 N2 N i=1 N j=1 yij; p u=1 q v=1 π2 uv µu.ν.v = N i=1 N j=1 xij xi. yij y.j ; Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 26 / 29 Relational Analysis Approach Relational Transfer Principle Using the ”Relational Transfer Principle” we get: N2 ρIND(X, Y ) = pq N i=1 N j=1 xijyij −p N i=1 N j=1 xij −q N i=1 N j=1 yij +N2 (15) Origin of the Indetermination Concept: when ρIND(X, Y ) = 0 we get: N i=1 N j=1 xijyij + N i=1 N j=1 ¯xij ¯yij Votes in favor = N i=1 N j=1 ¯xijyij + N i=1 N j=1 xij ¯yij Votes against Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 27 / 29 A new Graph modularization criterion Plan 1 Goal of the Presentation 2 The optimal transport problem: Monge and Monge-Kantorovich Problems 3 Extensions and variants of the MKP problem 4 Monge and Anti-Monge matrices and some related structural properties 5 Duality related to ”Independence” and ”Indetermination” structures 6 Relational Analysis Approach 7 A new Graph modularization criterion Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 28 / 29 A new Graph modularization criterion Graph Modularization Criteria The Newman-Girvan criterion: 1 2M N i=1 N i =1 aii − ai.a.i 2M xii The deviation to indetermination criterion: 1 2M N i=1 N i =1 aii − ai. N − a.i N + 2M N2 xii Jean-Franc¸ois Marcotorchino (Thales Communications et S´ecurit´e, TCS and LSTA, Paris 6)Optimal Transport and Minimal Trade Problem, Impacts on Relational Metrics and ApplicatioAugust 2013 29 / 29