matchingsmetoder

Matchingsmetoder är metoder för att konstruera matchningar, det vill säga uppsättningar av par där inga två par överlappar i en graf eller ett dataset. En matchning i en graf är en samling kanter där varje nod förekommer i högst en kant i matchningen. Begreppet används inom grafteori och inom statistisk metodik för att balansera eller para samman enheter med liknande egenskaper. En maximal matchning inte kan utökas genom att lägga till fler kanter, medan en maximal eller maximal viktad matchning uppfyller specifika mål, till exempel största möjliga antal kanter eller största totala vikt.

Inom grafteorin studeras algoritmer för att hitta olika typer av matchningar. För bipartita grafer finns effektiva algoritmer som Hopcroft–Karp som hittar en maximal kardinalitet med tidskomplexitet O(E sqrt(V)). För viktade bipartita grafer används ofta Hungarian-algoritmen för maximal viktad matchning. Generella grafer kräver Edmonds’ blossom-algoritm för maximal kardinalitet, medan viktade versioner av blossom-algoritmen används för maximal viktad matchning. Dessa metoder används i nätverksdesign, schemaläggning och andra tillämpningar där parning utan överlappningar är central.

Inom statistiken används matchningsmetoder för att skapa jämförbara grupper i observationsstudier och därmed minska konfunderingar. Vanliga metoder inkluderar propensity score matching (PSM), där enheten i olika grupper paras baserat på förutbestämda sannolikheter; exakt matching och koarserat exakt matching; Mahalanobis-distorionsbaserad matching; närmaste granne-matching och kaliperbaserad matching. Genetic matching kombinerar flera mått och optimerar balansen mellan grupperna. Dessa metoder syftar till att ge mer tillförlitliga uppskattningar av behandlingseffekter i icke‑randomiserade studier.