Trainspotting Extraction and Analysis of Traffic and Topologies of Transportation Networks

Networks

MaciejKurant,PatrickThiran

(Dated:February2,2008)

Theknowledgeofreal-lifetrafficpatterniscrucialforgoodunderstandingandanalysisoftrans-portationsystems.Thisdataisquiterare.Inthispaperweproposeanalgorithmforextractingboththerealphysicaltopologyandthenetworkoftrafficflowsfromtimetablesofpublicmasstrans-portationsystems.Weapplythisalgorithmtotimetablesofthreelargetransportationnetworks.Thisenablesustomakeasystematiccomparisonbetweenthreedifferentapproachestoconstructagraphrepresentationofatransportationnetwork;theresultinggraphsarefundamentallydifferent.Wealsofindthatthereal-lifetrafficpatternisveryheterogenous,bothinspaceandtrafficflowr 2006aMintensities.

PACSnumbers:89.75.Hc,89.75.Fb,89.40.Bb

42 I.INTRODUCTION

]phIntherecentyears,studiesoftransportationnetworks-chavedrawnasubstantialamountofattentioninthephysicscommunity.Thegraphsderivedfromthephysi-socalinfrastructureofsuchnetworkswereanalyzedonthe.sexamplesofapowergrid[1,2],arailwaynetwork[3,4],croadnetworks[5,6,7,8,9],pipelinenetwork[4]orurbanismasstransportationsystems[10,11,12,13,14].Theseystudieshaveoneimportantfeatureincommon-theyfo-hcusexclusivelyonthetopologyofthenetwork,andtheyp[donottakeintoaccountthereal-lifetrafficpattern.This makestheviewveryincomplete,becausecarryingtraf-2ficistheultimategoalofeverytransportationsystem.vFacingthelackofreal-lifetrafficdata,someauthorstry15toestimatethetrafficpatternbasedexclusivelyonthe1topology.Probablythemostcommonloadestimator0isbetweenness(usede.g.,in[15,16,17,18,19,20]),1whichassumesthateachpairofnodesexchangesthe5sameamountoftraffic.Butthereal-lifetrafficpatternsareinfactveryheterogenous,bothinspaceandtraffic/0sflowintensities.Thereforethemostimportantnodesandcedgesfromatopologicalpointofviewmightnotneces-issarilycarrythemosttraffic.In[21]weshowthatinytypicaltransportationnetworksthecorrelationbetweenhtherealloadandthebetweennessisverylow.Thereforep:itisessentialforsomeapplicationstoknowtherealtraf-vficpattern.

iXInterestingly,thenetworksoftrafficflowswerestudiedseparately,seetheexampleofflowsofpeoplewithinaracity[22],andcommutingtrafficflowsbetweendifferentcities[23].Thesestudies,inturn,neglecttheunderlyingphysicaltopology,makingtheanalysisincomplete.Forinstance,itisimpossibletodetectthemostloadedphys-icaledges,whichmighthaveacrucialmeaningfortheresilienceofthesystem.Acomprehensiveviewofthesystemoftenrequirestoanalyzebothlayers(physicalandtraffic)together.

Unfortunately,thedatasetsincludingbothphysicaltopologyandtrafficflowsarerathersparse,anddiffi-culttoget.Inthispaperweproposeanapproachtoextractthephysicalstructureandthenetworkoftraf-

ficflowsfromtimetables.Timetablesoftrains,buses,trams,metrosandothermeansofmasstransportation(henceforthcalledvehicles)arepubliclyavailable.Theyprovideuswiththeavailableconnectionsandtheirtimes.Timetablesalsocontaintheinformationaboutthephys-icalstructureofthenetworkandthetrafficflowsinit,but,asweshowlater,theyoftenrequireanontrivialpre-processingtoberevealed.

II.

SPACESANDTHEDIFFICULTYOFTHE

PROBLEM

Inordertopositionourcontributionintherangeofworksinthefield,webeginwithasystematicdefinitionofthetopologyoftransportationsystems.Thesetofnodesisdefinedbythesetofallstations(trainstations,busstops,etc).Itisnotobvious,however,whatshouldbeinterpretedasanedge.Itschoicedependsonwhatwewanttobereflectedbythetopologyofthephysicalgraph.Intheliteraturethereareessentiallythreeap-proachesthatdefinethreedifferent‘spaces’:herewecallthem‘space–of–changes’,‘space–of–stops’and‘space–of-–stations’:

Inspace–of–changes,twostationsareconsideredtobeconnectedbyalinkwhenthereisatleastonevehiclethatstopsatbothstations.Inotherwords,allstationsusedbyasinglevehiclearefullyinterconnectedandformaclique.Thisapproachneglectsthephysicaldistancebe-tweenthestations.Instead,intheresultingtopology,thelengthofashortestpathbetweentwoarbitrarystationsAandBisthenumberofchangesofmeanoftransporta-tiononeneedstogetfromAtoB[39].Thisapproachwasusedin[3,12,13];inthelattertheauthorsusedthetermspaceP.

Inspace–of–stops,twostationsareconnectediftheyaretwoconsecutivestopsonarouteofatleastoneve-hicle[13].Herethelengthofashortestpathbetweentwostationsistheminimalnumberofstopsoneneedstomake.Notethatthenumberofstationstraversedonthewaymightbelarger,becausethevehiclesdonotneces-sarystoponallofthem.

2

H

F

B

C

A

D

E

(b)

space–of–changes

G

o FA

B

H

G

D

C

E

(d)space–of–stations

FIG.1:(Coloronline)Anillustrationofthetransportationnetworktopologyinthreespaces.(a)Theroutesofthreevehicles.TherouteofLine2passesthroughnodeConthewayfromBtoD,butthevehicledoesnotstopthere.(b)Thetopologyinspace–of–changes.Eachrouteresultsinaclique.Anedgeisindicatedbytwocolors,whenitoriginatesfromtworoutes,butismergedintoasinglelink.(c)Thetopologyinspace–of–stops.The“shortcut”B-Disalegitimateedgeinthisspace.(d)Thetopologyinspace–of–stations.Thisgraphreflectsthetopologyofthereal-lifeinfrastructure.

Inspace–of–stations,twostationsareconnectedonlyiftheyarephysicallydirectlyconnected(withnostationinbetween).Thisreflectsthetopologyofthereal-lifein-frastructure.Here,thelengthofashortestpathbetweentwostationsistheminimalnumberofstationsonehastotraverse(stoppingornot).Thisapproachwasusedin[4,10,11,14].

InFig.1wegiveanillustrationofthethreespaces.Itiseasytoseethatthegraphinspace–of–stationsisasubgraphofthegraphinspace–of–stops,whichinturnisasubgraphofthegraphinspace–of–changes.Thetopologiesinspace–of–changesandspace–of–stopscanbedirectlyobtainedfromtimetables.Inspace–of–changes,foreachvehicle,wefullyconnectallstationsitstopsat.Thenwesimplifytheresultinggraphbydeletingmulti-edges.Inspace–of–stops,weconnectev-erytwoconsecutivestopsinroutesofvehicles.AsshowninFig.1c,thetopologyinspace–of–stopscanhaveshort-cutlinksthatdonotexistinthereal-lifeinfrastructure.Theseshortcutsshouldbeeliminatedinthespace–of-–stationstopology,whichmakesitmorechallengingtoobtain.Tothebestofourknowledge,theonlyworkonextractingtherealphysicalstructure(thetopologyinspace–of–stations)fromtimetableswasdoneinthecontextofrailwaynetworksinthePhDdissertationofAnnegretLebers[24].Theproposedsolutionfirstob-tainsthephysicalgraphinspace–of–stops.Next,specificstructuresintheinitialphysicalgraph,callededgebun-dles,aredetected.TheHamiltonpaths[40]withinthesebundlesshouldindicatethereal(non-shortcut)edges.Unfortunately,thebundlerecognitionproblemturnedouttobeNP-complete.Theheuristicsproposedin[24]resultinacorrectreal/shortcutclassificationof80%ofedgesinthestudiedgraphs.Theapproachweproposeinthispaperisbasedonsimpleobservationsthatwere

omittedin[24].Thisresultsinamuchsimplerandmoreeffectivealgorithm.

III.RELATEDWORK

Timetableshavebeenusedasadatasourceforanet-workconstructionin[3,13].However,thetopologiesobtainedintheseworkswereeitherinspace–of–changesorinspace–of–stops;neitherofthemreflectedthereal-lifeinfrastructure.Moreover,therealtrafficpatternswerenotconsideredinthesestudies.Thisisunderstand-able,becauseitisdifficulttointerpretatrafficflowinspacesofchangesandstops.Doesthe“traffic”onashortcutlinkhaveanyphysicalmeaning?Weknowthatthistrafficactuallytraversesothernon-shortcutlinksthatexistinreality.Incontrast,inspace–of–stations,thetrafficflowshaveclear,unambiguousandnaturalin-terpretation.

Anotherclassofnetworksthatcanbeconstructedwiththehelpoftimetablesareairportnetworks[6,25,26,27].There,thenodesaretheairports,andedgesaretheflightconnections.Theweightofanedgereflectsthetrafficonthisconnection,whichcanbeapproximatedbythenum-berofflightsthatuseitduringoneweek.Inthiscase,boththetopologyandthetrafficinformationareexplic-itlygivenbytimetables.Thisisbecausetheroutesofplanesarenotconstrainedtoanyphysicalinfrastructure,asopposedtoroadsforcarsorrail-tracksfortrains.Sothereareno“real”linksand“shortcut”links.Inasensealllinksarereal,andthetopologiesinspace–of–stopsandinspace–of–stationsactuallycoincide.

Inferringthespace–of–stationstopologyfromtimeta-blesbecomessimplealsoinanotherspecialcase,wherethevehiclesstopateachstationtheytraverse(e.g.,

inmanysubwaynetworks).Thisnaturallyeliminatestheshortcuts,makingthetopologiesinspace–of–stopsandstationsidentical.Thisisnottrueinageneralcase,withbothlocalandexpressvehicles.

Inthereminderofthispaper,weintroducenecessarynotationinSectionIV.Next,inSectionVwegiveanal-gorithmthatextractstherealphysicalstructure(atopol-ogyinspace–of–stations)andthenetworkoftrafficflowsfromtimetables.InSectionVIwetestouralgorithmontimetablesofthreelargetransportationnetworksatthreedifferentscales:city,countryandcontinent.Wealsoan-alyzetheresultingphysicaltopologiesandcomparethemwiththoseobtainedbyalternativeapproaches.Finally,inSectionVIIweconcludethepaper.

IV.NOTATIONA.

Twolayers

Wefollowthetwo-layerframeworkintroducedin[21].

Thelower-layertopologyiscalledaphysicalgraphGφ=(Vφ,Eφ),andtheupper-layerλtopologyiscalledalogicalgraphGλ=(Vλ,E).Weassumethatφthesetsofnodesatbothlayersareidentical,i.e.,Vand≡λVλ,butasageneralrule,wekeeptheindexesφtomakethedescriptionunambiguous.LetN=|Vφnumberofnodes.Everylogicaledgeeλ|==|Vλ{u|λ,bevλthemappedonthephysicalgraphasapathM(eλ)⊂}Gisφconnectingλthenodesuφandvφ,correspondingtouλandv.(Apathisdefinedbythesequenceofnodesittraverses.)ThesetofpathscorrespondingtoalllogicaledgesiscalledamappingM(Eλ)ofthelogicaltopologyonthephysicaltopology.

Inthefieldoftransportationnetworkstheundirected,unweightedphysicalgraphGφcapturesthetopologyofthephysicalinfrastructure(i.e.,inspace–of–stations),andtheweightedlogicalgraphGλreflectstheundirectedtrafficflows.Everylogicaledgeeλiscreatedbyconnect-ingthefirstandthelastnodeofthecorrespondingtrafficflow,andbyassigningaweightw(eλ)thatrepresentstheintensityλofthisflow.ThemappingM(eλ)oftheedgeeisthepathtakenbythisflow.

B.Timetabledata

Wetakealistofallvehiclesdepartinginthesystem

withinsomeperiod(e.g.,oneweekday).DenotebyR={ri}i=1..|R|thelistofroutesfollowedbythesevehicles,where|R|isthetotalnumberofvehicles.Arouteriofithvehicleisdefinedbythelistofnodesittraverses.Notethatsincethereareusuallymorevehicles(thanone)followingthesamepathononeday,someoftheroutesmaybeidentical.

3

V.

ALGORITHM

Thealgorithmhasthreephases.Inthefirstone,initialization,basedonthesetofroutesR,wecreatethesetofnodesVφ=Gφstop=(Vφ

,EφVλandthephysicaltopology

stop)inspace–of–stops.Inthesecond,

mainphase,thesetsRandEφ

detectinganderasingthestopareiterativelyre-finedbyshortcutlinksinthephysicalgraphGφstop,resultinginthephysicaltopology

Gφstat=(Vφ

,Eφwestat)inspace–of–stations.Finally,inthethirdphase,groupthevehicleswithidenticalroutes,andobtainthelogicalgraphGλandthemappingM(Eλ)ofthelogicaledgesonthephysicalgraphGφbeloweachphaseseparately.

stat.Wede-scribeA.

Phase1-initialization

Inthisphaseweinterpreteverytwoconsecutivenodesinanyrouteriweconnectthese∈Rnodesasdirectlywithalink,connected.whichcanConsequently,bewrittenas

Eφ

stop=

󰀁E(ri)i=1..|R|

whereE(ri)isthesetofallpairsofadjacentnodesinri

(i.e.,alledgesinri).Thisresultsinthephysicaltopology

Gφstop=(Vφ

,Eφstop)inspace–of–stops.

B.

Phase2-deletingshortcuts

Inthisphase,ateachiteration,wedetectashortcutinthesetofphysicaledges,deleteit,andupdaterithatusethisshortcut.Denotebyeφeφ

allroutes

(1),(2)thetwoend-nodesofeφ,andbyRev(Peφ)thereversedversionofPeφ(thesequencefromthelastnodetothefirstone).Thealgorithmisasfollows:

1.Eφstat:=Eφstop

2.Findatuple(eφ,ri)suchthateφisashortcutforri:

eφ(1)∈riandeφ

(2)∈ri

andeφ∈/E(ri).3.IFno(eφ,ri)foundTHENRETURNEφstatandR.4.Peφ:=subpathofrifromeφφ(1)toe(2)

5.FORallrj•∈RDO:

•IfIf((eeφ,eφ

(1)(2))∈rjTHENreplaceitwithPeφ

φφ

(2),e(1))∈rjTHENreplaceitwithRev(Peφ)

6.Eφstat:=Eφstat\\{eφ}

7.GOTO2

InStep2,welookforaphysicalφlinkthatisashort-cut.Wedeclareaphysicallinketobeashortcut,ifthereexistsarouterinonconsecutivenodesin∈Rri,.suchForthatexample,eφconnectstwoinFig.1c,eφ={B,D}isashortcutbecauseitconnectstwonotneighboringnodesintherouter1ofLine1.Ifnophysi-caledgecanbedeclaredinStep3,returningEφ

ashortcut,thealgorithmquits

statandR.Otherwise,inStep4,wefindthepathPeφthatthisshortcutshouldtake.InFig.1cthispathisPeφ=(B,C,D).InStep5,weup-dateφthesetofroutesRbyreplacingeveryshortcutlinkeineveryrouteusingitwiththecorrespondingpathPeφ.Inourexample,theupdatedrouteofLine2be-comesr2=(A,B,C,D,E).ItisthusidenticaltotherouteofLine1.Finally,inStep6wedeletetheshort-cuteφfromthephysicalgraph.Weiteratethesestepsuntilnoshortcutisfound(Step2).Theresultingphys-icalgraphGφstat=(Vφ

,Eφstat)⊂Gφstop,isagraphinspace–of–stations.

C.

Phase3-groupingthesameroutestogether

Finally,basedonthelistRofroutesupdatedinphase2,wefindgroupsofvehiclesthatfollowthesamepath(inλanydirection).Eachsuchgroupdefinesoneedgeeinthelogicalgraph;eλconnectsthefirstandthelastnodeoftheroute.Thenumberλofvehiclesthatfollowthisroutebecomestheweightw(e)ofthelogicaledgeeλ;therouteitselfbecomesthemappingM(eλ)ofeλonthephysicalgraph.

Denotebyri(first),ri(last)thefirstandthelastnodesinri,andbyE(M(eλ))thesetofallphysicaledgesinthemappingofeλ.Now,Phase3canbestatedasfollows:1.Eλ=∅,M=∅

2.FORi=1TO|R|DO:•eλi={ri(first),ri(last)•IFELSEeλi∈λw(}

eλEEλTHEN=Eλ󰀂{eλi):=w(eλ

ii},M(eλ)+1i)=ri,w(eλi)=1

3.Eφ

stat=󰀂eλ∈EλE(M(eλ))IntheexampleinFig.1,afterphase2theroutesofLine1andLine2becomeidentical;thereforeinphase3theyaregroupedtogetherdefiningalogicalwiththeweightw(eλ

edgeeλthemapping1={A,E}

1)=2andM(eλ(A,B,C,D,E).Asecondlogicaledgeiseλ

1)=

w(eλ(e2={F,H}

with2)=1andMλ

2)=(F,B,G,H).

D.

Accuracyofthealgorithm

Therearepotentialsourcesofmistakesandinaccura-ciesinourapproach.First,thelinksthatwedeleteasbeingshortcuts,mightactuallyexistinreality.However,acomparisonoftheresultsofouralgorithmwiththerealmaps(seeSectionVI)revealsveryfewdifferences,which

4

meansthatthissourceoffailuresoccursveryrarelyinrealdatasets.

Asecondproblemliesintheestimationofthetrafficpattern.Interpretingtheroutesoftrains,buses,trams,metros,etc,astrafficflowsgivesusapictureatalowlevelofgranularity.Wevieweveryvehicleasatrafficunit,regardlessofitssizeorthenumberofpeopleitcar-ries.Moreover,peopleusuallyusethesevehiclesonlyonaportionofitstotaljourney,notfromthefirsttothelaststation.Clearly,thevehicleroutesaretheresultofanoptimizationprocessthattakeintoaccountmanyfactors,suchaspeople’sdemand,continuityofthepath,travel-ingtimesandavailabilityofstock.However,webelievethattheyreflectwellthegeneraldirectionandintensityoftravels,andwetakeavehicleasabasictrafficunit.Afterall,thesearethevehiclesthatappearontheroadsandcausetraffic,notthepeopletheytransport.

VI.

ASTUDYOFTHREEREAL-LIFE

NETWORKS

Inthissectionweapplyouralgorithmtoextractthe

datafromthetimetablesofthreeexamplesoftransporta-tionnetworks,withsizesrangingfromcitytocontinent.Asanexampleofacity,wetakethemasstransporta-tionsystem(buses,tramsandmetros)ofWarsaw(WA),Poland;itstimetablesareavailableat[28].Atacountrylevel,westudytherailwaynetworkofSwitzerland(CH).Finally,weinvestigatetherailwaynetworkformedbymajortrainsandstationsinmostcountriesofcentralEurope(EU)[41].ThetimetablesofbothCHandEUnetworksareavailableat[29].ThebasicparametersofthedatasetsandoftheresultinggraphscanbefoundinTableI.

Thissectionisorganizedasfollows.First,wefocusonaparticulardatasetinordertostudytheperformanceofouralgorithm.Next,weanalyzeandcomparethephys-icalgraphsoriginatingfromallthreedatasetsineachoftheconsideredspaces.Finally,wefocusourattentiononthelogicalgraphsandtrafficflowsextractedbyouralgorithm.

A.

Anexample:Therailwaynetworkof

Switzerland(CH)

Asanillustration,letusconsidermorecloselytherailwaynetworkofSwitzerland(CH).Accordingtoourtimetable,onatypicalweekdaythereare|R|=6957differenttrainsthatfollow|Eλ(usuallythereismorethanone|train=505followingdifferenttheroutessamerouteduringoneday).OurdatacontainsN=1613stationsinSwitzerland,togetherwiththeirphysicalco-ordinates.InFig.2wepresentthegraphsobtainedfromthisdataset.ThephysicalgraphsinthethreespacesareshowninFigs.2abc.Thegraphinspace–of–stationswasobtainedwiththehelpofthealgorithmintroduced

5

(a)PhysicalgraphGφchangeinspace–of–changes(b)PhysicalgraphGφstopinspace–of–stops

(c)PhysicalgraphGφstatinspace–of–stations

(d)Realphysicalmap

(e)Logicalgraph

FIG.2:TherailwaynetworkinSwitzerland(CH).(a,b,c)Physicalgraphsinspace–of–changes,stopsandstations,respectively.

(d)TherealmapoftherailtracksinSwitzerland.(e)Thelogicalgraph.Everyedgeconnectsthefirstandthelaststationofaparticulartrainroute;itsweightreflectsthenumberoftrainsfollowingthisrouteinanydirection.

6

General

Area[km2]

WA(Warsaw)

41’300

EU(Europe)

48531533

Physicalgraph

|R|Space󰀂kφ󰀃󰀂lφ󰀃

784374

221224976

183290

changes24.63.6

6’957stops2.416.3

stations2.146.6

883298

6703860048

5765184

0.6829

0.16810.0092

0.73470.34010.0129

TABLEI:Thestudieddatasets.“Area”isthesurfaceoccupiedbytheregioncoveredbythenetwork.Nisthenumberofnodes(stations/stops).|R|isthetotalnumberofvehiclesdepartinginthenetworkduringoneweekday.|Eλ|isthenumberofedgesinthelogicalgraph(numbertrafficflows);itismuchsmallerthan|R|,becausethevehiclesfollowingthesameroutearegroupedtogetherinphase3ofouralgorithm.AlltheremainingparametersarecomputedforthephysicalgraphsGφ:|Eφ|isthenumberofedges,󰀂kφ󰀃istheaveragenodedegree,dφstandsforthediameter,󰀂lφ󰀃istheaverageshortestpathlength,andcφistheclusteringcoefficient.

intheprevioussection.Thenumberofverticesisthesameinallthreespaces.Thenumberofedgesinspace-φ

–of–changes,|Echange|=19827,ismuchlargerthanintheothertwospaces.Althoughatfirstsightthephysicalgraphsinspace–of–stationsandinspace–of–stopslookcomparable,thelatterhasanumberof(nonexistinginreality)shortcutlinks.Foravisualverificationofcor-rectnessofouralgorithm,weshowinFig.2dtherealmapoftheSwissrailwaysystem;weobserveonlyminordifferencesbetween(c)and(d).Finally,inFig.2e,wepresentthelogicalgraphthatreflectsthetrafficflowsinthenetwork.Thisgraphisveryheterogenousbothintheweightsofedgesandinthelayoutoftraffic.

B.Thephysicalgraphinthreespaces

Howdoesthechoiceofspaceaffectthetopology?Westudyinthissectionthephysicalgraphsinthethreespaceswithrespecttothebasicmetricsoftenusedintheanalysisofcomplexnetworks.

Diameterdφ,andaverageshortestpathlength󰀂lφ󰀃

1.

Theaverageshortestpathlength󰀌l󰀍iscomputedoverthelengthsofshortestpathsbetweenallpairsofvertices.Thediameterdisthelongestofallshortestpathlengths.Theseparametersareusuallycloselyrelated.

Thediametersandaverageshortestpathlengthsofthegraphs√inspace–of–stationsarelarge,andscaleroughlyas

10󰀁1)φ10󰀁2k(rP10󰀁30200400600kφ

(b)space–of–stops

(Gφstop)

10010󰀁1)φk(10󰀁2rP10󰀁302468kφ

(d)space–of–stops,

log-logscale

FIG.3:Nodedegreedistributionsinphysicalgraphsinthethreespaces,forthedatasetsWA,CHandEU.Plots(a-c)useasemi-logarithmicscale,plot(d)usesalog-logscale.Ifnecessary,thedataislin-binnedorlog-binned,accordingly.

3.Clusteringcoefficientsc

Wehavestudiedtheclusteringcoefficientscdefinedasaprobabilitythattworandomlychosenneighborsofanodearealsodirectneighborsofeachother[30].

Theclusteringcoefficientoftopologiesinspace–of–changesareveryhigh,whichisadirectconsequenceofaveryhighdensityandexistenceofmanycliques.Whatismoreinterestingisthatinallthreedatasets,theclus-teringcoefficientinspace–of–stopsis1-2ordersofmag-nitudelargerthaninspace–of–stations.Asinthecaseofthegraphdiameter,hereagaintheshortcutlinksturnoutplayaveryimportantroleinthetopology.

C.

Trafficflowsandthelogicalgraph

Nowweturnourattentiontothetrafficthatflowsinournetworks.Weextractedthisscarcedatawiththehelpofthealgorithmintroducedinthispaper.Aswear-guedbefore,theinterpretationoftrafficflowingthroughnetworksinspace–of–changesandstopsisrathercum-

7

12012012010010010080

80806060604040402020

20001020304050001020304050001020304050(a)WA(b)CH(c)EU

FIG.4:Thelengthsoforiginaltimetableroutes(xaxis)

versustheselengthsaftertheapplicationofouralgorithm(yaxis).Allthreedatasetsaredrawninthesamescale.

bersome.Thereforewerestrictouranalysistothetrafficflowstraversingthephysicalgraphinspace–of–stations.InFig.4wecomparethelengthsoftrafficflowsbeforeandafterapplicationofouralgorithm.Anewtrafficflowcanbeeitherequalinlengthtotheoriginalone(ifnoshortcutwasdetectedonitspath),orlonger.Weobservethatforallthreedatasets,thereisasignificantnumberofflowsthatbecomelonger.Insomecasesthisincreaseinlengthisbyasmuchas10times.Generally,thelongertheoriginalflowis,thelessextendeditgetsduringarunofouralgorithm.Thisisexpected,becausealongflowinatimetableusuallycorrespondstoalocaltrainthatstopsatallstations(i.e.,usesnoshortcuts).InFig.5wepresentbasicdistributionsmeasuredforlogicalgraphsinthethreedatasets.Recallthattheedgesinalogicalgraphreflectthetrafficflows.There-fore,thenodedegreekλisthenumberofdifferentcon-nectionsstarting/endingatthecorrespondingstation(Fig.5a).Thestrengthsλofanodeisthesumoftheweightsofneighboringedges[25];hereitisthenumberofallconnectionsstarting/endingatthisstation(Fig.5b).Finally,theweightw(eλ)ofalogicaledgeisthetrafficflowintensity(Fig.5c).

Allthreedistributionsareheavilyright-skewedmeaningthatthereisasmallnumberofnodes/edgeswithveryhighvaluesoftheobservedparameter.Weconcludethatthereal-lifetrafficpatternsareveryheterogenous,bothinspace(nodedegreeandstrength)andtrafficflowin-tensities.Thiswasshownin[21]tobethereasonofhighunpredictabilityofloaddistributionintransporta-tionnetworks.

VII.CONCLUSIONS

Theknowledgeofreal-lifetrafficpatterniscrucialintheanalysisoftransportationsystems.Thisdataisusu-allymuchmoredifficulttogetthanthepuretopologyofanetwork.Inthispaperwehaveproposedanalgo-rithmforextractingboththephysicaltopologyandthenetworkoftrafficflowsfromtimetablesofpublicmasstransportationsystems.Wehaveappliedouralgorithm

8

10010󰀁110󰀁310󰀁410󰀁5100101102Pr(sλ)10󰀁2sλ

(b)Nodestrengths

10010󰀁110󰀁210󰀁310󰀁410󰀁510010110210322publictransportnetworksinPoland.Phys.Rev.E,72:046127,2005.[14]I.Vragovi´c,E.Louis,andA.Diaz-Guilera.Efficiencyofinformationaltransferinregularandcomplexnetworks.Phys.Rev.E,71:036122,2005.

[15]K.-I.Goh,B.Kahng,andD.Kim.Universalbehaviorofloaddistributioninscale-freenetworks.Phys.Rev.Lett.,87(27):278701,December2001.[16]G.Szab´o,M.Alava,andJ.Kert´esz.Shortestpathsandloadscalinginscale-freetrees.Phys.Rev.E,66:026101,2002.

[17]B.Bollob´asandO.Riordan.Shortestpathsandloadscalinginscale-freetrees.Phys.Rev.E,69(3):036114,March2004.

[18]P.HolmeandBeomJunKim.Vertexoverloadbreak-downinevolvingnetworks.Phys.Rev.E,65:066109,2002.

[19]L.Zhao,K.Park,andY.-C.Lai.Attackvulnerabilityofscale-freenetworksduetocascadingbreakdown.Phys.Rev.E,70:035101(R),2004.

[20]AdilsonE.Motter.Cascadecontrolanddefenceincom-plexnetworks.Phys.Rev.Lett.,93(9):098701,2004.[21]M.KurantandP.Thiran.Layeredcomplexnetworks.physics/0510194,acceptedinPhys.Rev.Lett.,2005.[22]G.Chowell,J.M.Hyman,S.Eubank,andC.Castillo-Chavez.Scalinglawsforthemovementofpeoplebetweenlocationsinalargecity.Phys.Rev.E,68:066102,2003.[23]

AndreaDeMontis,MarcBarth´elemy,AlessandroChessa,andAlessandroVespignani.Thestructureofinter-urbantraffic:Aweightednetworkanalysis.physics/0507106,2005.

[24]AnnegretLiebers.AnalyzingTrainTimeTableGraphs.PhDthesis,UniversityofKonstanz,DepartmentofCom-puterandInformationScience,2001.[25]A.Barrat,M.Barth´elemy,R.Pastor-Satorras,andA.Vespignani.Thearchitectureofcomplexweightednet-works.Proc.Natl.Acad.Sci.USA,101(11):3747,2004.[26]L.Hufnagel,D.Brockmann,andT.Geisel.Forecastandcontrolofepidemicsinaglobalizedworld.Proc.Natl.Acad.Sci.USA,101(42):15124,2004.[27]

R.Guimer`a,S.Mossa,A.Turtschi,andL.A.N.Amaral.Theworldwideairtransportationnetwork:Anomalouscentrality,communitystructure,andcities’globalroles.

9

Proc.Natl.Acad.Sci.USA,102:7794,2005.[28]http://www.ztm.waw.pl.[29]http://www.sbb.ch.

[30]D.J.Watts.SmallWorlds.PrinctonUniversityPress,1999.

[31]JonKleinberg.Thesmall-worldphenomenon:Anal-gorithmicperspective.Proc.32ndACMSymposiumonTheoryofComputing,2000.[32]StevenH.Strogatz.Exploringcomplexnetworks.410:268,2001.

[33]R.Albert,H.Jeong,andA.-L.Barabsi.Errorandattacktoleranceincomplexnetworks.Nature,406:378,2000.[34]NaokiMasuda,HiroyoshiMiwa,andNorioKonno.Ge-ographicalthresholdgraphswithsmall-worldandscale-freeproperties.Phys.Rev.E,71:036108,2005.

[35]ThomasPetermannandPaoloDeLosRios.Spa-tialsmall-worldnetworks:Awiring-costperspective.cond-mat/0501420,2005.

[36]

AlainBarrat,MarcBarthelemy,andAlessandroVespig-nani.Theeffectsofspatialconstraintsontheevolutionofweightedcomplexnetworks.J.Stat.Mech.,pageP05003,2005.

[37]http://icawww.epfl.ch/kurant/.

[38]VamsiKalapala,VishalSanwalani,AaronClauset,andCristopherMoore.Scaleinvarianceinroadnetworks.physics/0510198,page2005.

[39]

Inthissense,agraphinspace–of–changesiscloselyrelatedtothedualinterpretationofurbanroadnet-works[5,7,38],wherestreets(ofagivenname)maptonodes,andintersectionsbetweenstreetsmaptolinksbetweenthenodes.Inatransportationnetworkinspace-–of–changes,thelengthofashortestpathisthenumberofchangesofmeanoftransportation,whereasthelengthofashortestpathinadualgraphofacityisthenumberofchangesofstreetsonthewayfromthestartingpointtodestination.

[40]Hamiltonpathisapaththatpassesthrougheveryvertexofagraphexactlyonce

[41]

IntheEUdataset,Parishasoriginallyseveralstationsthatarenotdirectlyconnectedbetweeneachother.Fol-lowingtheapproachin[4],wemergedthemintoonecom-monnode.