Enviaments etiquetats ‘Mathematica’

desembre 6, 2011

Els sistemes D’Hondt i Sainte-Laguë

El conegut —i criticat— sistema D’Hondt, l’utilitzat a Espanya, és un mètode de representació que assigna escons proporcionalment als resultats obtinguts per llistes de partits. És de la família dels mètodes de les “mitjanes més altes“, que inclou també el mètode Sainte-Laguë.

En aquests mètodes, els vots que rep cada partit es divideixen per una successió de divisors, obtenint una llista de quocients. Els escons s’assignen llavors als quocients més elevats, garantint una certa proporcionalitat. La diferència entre els divisors utilitzats dóna lloc a mètodes diferents: en el cas D’Hondt, s’utilitza la successió 1, 2, 3…, mentre que pel Sainte-Laguë s’utilitza 1, 3, 5… Així, la manera de calcular els quocients Q_s de cada partit en aquests dos mètodes és

Q_s = \frac{V}{a s + 1},

on V és el número total de vots del partit en qüestió, s és el número d’escons que aquest partit ja ha rebut (començant des de 0) i a és un coeficient que depèn del mètode (a=1 per el sistema D’Hondt i a = 2 pel Sainte-Laguë). El D’Hondt tendeix a donar als partits majoritaris una sobre-representació en la proporció d’escons respecte la proporció de vots, mentre que el Saint-Laguë respecta més la proporcionalitat.

Aquests sistemes sovint es modifiquen introduint un llindar, de manera que una llista que no obté aquest llindar no entra a la repartició d’escons. En el cas de les estatals espanyoles, el llindar és del 3% del total de vots en cada circumscripció electoral (que corresponen a les províncies).

Les següents funcions per a Mathematica simulen la repartició d’escons. Els paràmetres són vots, que és una llista dels vots obtinguts per cada partit amb el format

{{"Partit A", votsA}, {"Partit B", votsB}, ...}

n, que és el total d’escons a repartit i llindar (opcional, per defecte 0), que és la fracció mínima per entrar a la repartició (en el cas de les estatals espanyoles, com he dit abans, 0.03).

DHondt[vots_List, n_Integer, llindar_: 0] := Module[
  {taula, tall, votsTotal},

  votsTotal = Plus @@ vots[[All, 2]];

  taula = Table[
    {
     vots[[i, 1]],
     If[vots[[i, 2]] >= (llindar votsTotal),
        vots[[i, 2]]/#,
        0
        ] & /@ Range[n]
     }, {i, 1, Length[vots]}
    ];

  tall = Sort[Flatten[taula[[All, 2]]], Greater][[n]];

  Table[{
    taula[[i, 1]],
    Count[taula[[i, 2]], a_ /; a >= tall]
    }, {i, 1, Length[taula]}
   ]
  ]
SainteLague[vots_List, n_Integer, llindar_: 0] := Module[
  {taula, tall, votsTotal},

  votsTotal = Plus @@ vots[[All, 2]];

  taula = Table[
    {
     vots[[i, 1]],
     If[vots[[i, 2]] >= (llindar votsTotal),
        vots[[i, 2]]/(2 # + 1),
        0
        ] & /@ Range[0, n - 1]
     }, {i, 1, Length[vots]}
    ];

  tall = Sort[Flatten[taula[[All, 2]]], Greater][[n]];

  Table[{
    taula[[i, 1]],
    Count[taula[[i, 2]], a_ /; a >= tall]
    }, {i, 1, Length[taula]}
   ]
  ]

Actualització (07/12/2011): He tret el Floor[], que com diu en Bernat en un comentari no té sentit.

octubre 17, 2010

Jugant amb la funció CountryData[] del Mathematica

Buscant coses per l’ajuda del Mathematica, avui he trobat la funció CountryData i hi he estat jugant una mica. Resulta que conté un munt d’informació sobre els països del món, i que a més hi ha funcions similars com CityData. Us en posaré un exemple senzill: construïm un graph on els vèrtexs són els països llistats a CountryData, i una aresta uneix dos països si aquests són veïns. Per fer-ho una mica més atractiu visualment, pintarem els vèrtexs en funció del continent al qual pertanyen d’acord amb els colors del Risk. Les arestes tindran també el color del continent si uneixen dos països del mateix continent, o gris si serveixen de pont entre dos continents.

Primer ens fem una funció per a assignar un color a cada continent:

RiskColorsList = {
 {"Africa", Darker[Brown]},
 {"Asia", Darker[Green]},
 {"Europe", Darker[Blue]},
 {"NorthAmerica", Darker[Yellow]},
 {"Oceania", Darker[Purple]},
 {"SouthAmerica", Darker[Red]}
 };

RiskColor[continent_] := If[MemberQ[RiskColorsList[[All, 1]], continent],
  Select[RiskColorsList, #[[1]] == continent &][[1, 2]]
  ,
  Black
  ]

Ara ja podem dibuixar el graf amb tots els països,

GraphPlot[
  Flatten[Thread[# -> CountryData[#, "BorderingCountries"]] & /@
     CountryData[]]~Join~Flatten[{# -> #} & /@ CountryData[]],
  VertexLabeling -> Tooltip, MultiedgeStyle -> None,
  SelfLoopStyle -> None,
  VertexRenderingFunction -> ({PointSize[Large],
      RiskColor[CountryData[#2, "Continent"]],
      Tooltip[Point[#1], #2]} &),
  EdgeRenderingFunction -> ({If[
       CountryData[#2[[1]], "Continent"] !=
        CountryData[#2[[2]], "Continent"], Gray,
       RiskColor[CountryData[#2[[1]], "Continent"]]], Line[#1]} &),
  ImageSize -> Large
  ]

Queden els continents força ben delimitats, oi? Oceania, de color lila, destaca poc perquè els països tenen pocs veïns. Podem situar els vèrtexs al que seria el centre geogràfic de cada país, a veure si el graf agafa una mica la forma dels continents:

GraphPlot[
 Flatten[Thread[# -> CountryData[#, "BorderingCountries"]] & /@
    CountryData[]]~Join~Flatten[{# -> #} & /@ CountryData[]],
 VertexLabeling -> Tooltip, MultiedgeStyle -> None,
 SelfLoopStyle -> None,
 VertexCoordinateRules ->
  Flatten[{# -> ({#2, #1} & @@
         CountryData[#, "CenterCoordinates"])} & /@ CountryData[]],
 VertexRenderingFunction -> ({PointSize[Large],
     RiskColor[CountryData[#2, "Continent"]],
     Tooltip[Point[#1], #2]} &),
 EdgeRenderingFunction -> ({If[
      CountryData[#2[[1]], "Continent"] !=
       CountryData[#2[[2]], "Continent"], Gray,
      RiskColor[CountryData[#2[[1]], "Continent"]]], Line[#1]} &),
 ImageSize -> Large
 ]

Prou bé. Posem-hi el mapa del món per sota:

Show[CountryData["World", "Shape"], %]

Ecco fatto. No queda del tot ben centrat, però aquesta és la idea. Hi ha moltes més dades, a més. Seria divertit per exemple fer el graf dels països relacionats per llengües, per importacions i exportacions, etc. Un altre dia.

maig 5, 2010

Símbol copyleft al Mathematica

Estava mirant els símbols que té el Mathematica i he vist que hi ha el copyright, \[Copyright], però evidentment no el copyleft. Provant una mica he vist que es pot aconseguir ràpidament amb Rotate[\[Copyright], 180 Degree]. El resultat queda girat i no reflexat, que no és perfecte, però fa el fet. El problema és que llavors no es pot utilitzar com a símbol per assignar-li un valor. Ja sé que són ganes utilitzar-lo així, però amb el copyright sí que es pot fer i això sempre em pica una mica. De totes maneres, tampoc no està en format text, sinó que cal fer primer Text[Rotate[\[Copyright], 180 Degree]] per a poder-lo utilitzar com a cadena. Per exemple, Text[Rotate[\[Copyright], 180 Degree]] <> " 2010".

Algú s’ha trobat amb el mateix? Com ho solucioneu? Sabeu si es poden crear símbols nous? No n’he sabut trobar res a l’ajuda.

Etiquetes: , ,
maig 2, 2010

La funció W de Lambert

Algú havia vist alguna vegada la funció W de Lambert? Al Mathematica potser l’heu vist amb el nom de ProductLog. Apareix en llocs força diferents, entre ells la combinatòria. Es defineix com la funció inversa de f(w) = w e^w, és a dir, com la funció W que compleix z = W(z) e^{W(z)}, on z és un número complex. I se sol utilitzar per expressar solucions d’algunes equacions trascendentals.

M’ha sortit al mirar-me la solució de la component gegant S d’un graf Erdős-Rényi. En aquests grafs, la mida relativa (o la probabilitat) de la component gegant és S = 1 - e^{-zS} [1], on z és el grau mig del graf. Utilitzant la funció W, la solució no trivial (S\neq0) d’aquesta equació trascendental és S = 1 + \frac{1}{z} W(-ze^{-z}). Hi ha alguns valors exactes coneguts d’aquesta funció W que poden resultar força útils. Per exemple, sabent que W(-e^{-1}) = -1 veiem el resultat conegut del llindar de percolació, z=1.

La mida S de la component gegant d'un graf Erdős-Rényi en funció del grau mig z.

Prometo una explicació de la percolació algun dia d’aquests… si m’hi animo…

Referències

[1] Mark E. J. Newman, Steven H. Strogatz, and Duncan J. Watts, “Random graphs with arbitrary degree distributions and their applications“, Physical Review E (Statistical, Nonlinear, And Soft Matter Physics) 64, 026118 (2001). eprint: arXiv cond-mat/0007235.

febrer 16, 2010

Mons petits

Les Small World són xarxes on dos nodes qualssevol estan separats només per un número petit de passos, de salts d’un node a un altre. Aquest efecte va començar a ser estudiat a finals dels 60, quan Stanley Milgram, un psicòleg social que va dur a terme un experiment per determinar cadenes de relacions als Estats Units.

L’experiment de Milgram consistia en repartir paquets a persones aleatòries de les ciutats de Omaha, Nebraska i Wichita, a Kansas, amb instruccions d’enviar-les directament a certes persones de Boston si les coneixien directament, o en cas contrari d’enviar-les a algú que ells pensessin que podria conèixer aquestes persones. Al final, Milgram recollia els paquets i observava quants passos havia fet abans d’arribar a destianció. Milgram va arribar a la conclusió que les persones estaven separades per només 6 passos de mitja (els famosos 6 graus de separació, tot i que ell no va utilitzar aquest terme).

Tot i que els seus experiments han rebut moltes crítiques pel que fa a la veracitat o precisió, sí que és veritat que van significar un gran impuls per l’estudi de les xarxes, no només en el camp de les xarxes socials sinó en general, i que l’”efecte small world” s’ha confirmat en diverses xarxes.

Actualment, es considera que els xarxes que presenten un efecte small world són aquelles en les quals la distància típica que separa dos nodes (el número d’enllaços que cal recórrer per arribar d’un a l’altre) creix només com el logaritme del número total de nodes de la xarxa. Hi ha diversos tipus de xarxes que satisfan aquest requisit, per exemple les xarxes completament aleatòries, però no totes són una bona representació de les xarxes socials que trobem a la realitat. Aquestes xarxes socials, en canvi, es caracteritzen també per tenir un elevat nivell de “clustering”: és més probable que dues persones (dos nodes de la xarxa social) siguin amigues si ambdues comparteixen un altre amic en comú. El 1998, Duncan Watts i Steven Strogatz van proposar un model que presentava les dues propietats: un alt nivell de clustering, i a la vegada una separació típica petita. A aquest model se l’ha anomenat tant “small-world model” com “Watts-Strogatz model”, i té diverses versions.

Una d’aquestes versions, interessant perquè se’n poden calcular diverses propietats fàcilment, és la següent. Es distribueixen els nodes en un cadena unidimensional de longitud N, i cada node es connecta mitjançant un enllaç amb els seus veïns més propers fins a una distància k. És a dir, un determinat node v estarà connectat amb els nodes v-k, v-k+1, \ldots, v+k (sense incloure’s a ell mateix). Al crear aquesta “xarxa base”, es pot considerar que està tancada sobre si mateixa formant un anell, tot i que per derivar els resultats es considera llavors que N tendeix cap a infinit. Una vegada tenim la xarxa base, s’afegeix un enllaç “drecera” amb probabilitat \phi per cada enllaç original de la xarxa base, de manera que al final queden una mitjana de \phi kN dreceres. Cristopher Moore i Mark Newman tenen aquest article a PRE (arXiv cond-mat/0001393), que trobo molt interessant, que analitza les propietats de percolació d’aquest model en concret.

Per a qui hi vulgui jugar una mica, aquí us poso una funció del Mathematica que genera aquest model. En aquest cas, size és la mida N de la xarxa, k la distància màxima k dels veïns de la xarxa base i prob la probabilitat \phi de cada drecera.

SmallWorldAddedShortcutsGraph[size_,k_,prob_] := Module[
	{g,i,AddShortcut},

	AddShortcut[graph_] := Module[
		{v=V[graph],source,target},

		source=RandomInteger[{1,v}];
		target=RandomInteger[{1,v}];
		While[MemberQ[NeighborhoodVertices[graph,source,1],target],
			target=RandomInteger[{1,v}]
		];

		AddEdge[graph,{source,target}]
	];

	g = If[2k>=size,CompleteGraph[size],Harary[2k,size]]
	For[i=0,i<size*k,i++,
		If[RandomReal[]<prob,
			g=AddShortcut[g]
		]
	];

	g
]
Follow

Get every new post delivered to your Inbox.

Join 117 other followers