I afsnittet BOMS har vi gennemgået hvordan vi ved hjælp af almindelig grafteori og i særdeleshed Breadth First Search (BFS) algoritmen kan løse fejlfindingsproblemet.
En egenskab ved BOMS er hvorledes vi, efter at have fundet den umiddelbare forklaring , evaluerer alternative forklaringer der befinder sig nær den umiddelbare forklaring.
Disse alternative forklaringer bliver beregnet ved at udvælge knuder der befinder sig inden for en fast defineret afstand fra de fejlmeldte knuder. Alle kombinationer af de udvalgte knuder, sammenholdt med fejlrapporten, udgør de alternative forklaringer.
SU
Udvælgelsen af knuder til alternative forklaringer foregår på følgende måde. De fejlramte knuder, F, benyttes som kilder i BFS til at finde alle knuder, W, der ligger maksimalt r kanter væk fra mindst en knude i F. Det gælder da at W ≤V − F . I praksis er det ofte et fåtal af det samlede antal knuder der er fejlramt, dvs. F <<V . Dette betyder at W potentielt kan være næsten alle knuder i grafen. I forbindelse med disse test er det derfor rimeligt at antage W ≈V i værste fald. Den faktiske størrelse af W afhænger af to ting:
1. W afhænger af r, det maksimale antal kanter en udvalgt knude må ligge fra en fejlramt knude f F
W w∈
∈ .
2. W afhænger af grafens struktur og især grafens grad.
Figur 61 viser hvorledes størrelsen af W afhænger af r.
Figur 61: Udvælgelsen af knuders afhængighed af den maksimale afstand, r, fra en fejlramt knude.
Størrelsen af W afhænger også af grafens grad, dvs. det gennemsnitlige antal kanter fra hver knude. Grafen på Figur 62 er af højere grad end grafen på Figur 61. Sammenholdes størrelsen af W for ens værdier af r på de to grafer, ses det at størrelsen af W for en given værdi af r er betydeligt større på Figur 62.
Figur 62: Udvælgelsen af knuders afhængighed af grafens grad.
11.1.1 Afhængighed af r
Ved at generere et antal testgrafer, hver med 1000 knuder og et gennemsnit på tre kanter mellem hver knude, dvs. grad tre, kan man vise at W afhænger af r. I hver graf vælges 10 knuder tilfældigt til at være fejlmeldte, hvorefter antallet af udvalgte knuder findes for forskellige værdier af r. Resultatet kan ses på Figur 63. Det fuldstændige datasæt kan desuden ses i Appendiks 3.
1 2 3 4 102
103
r
|W|
Figur 63: Antallet af udvalgte knuder som funktion af en fast defineret afstand.
På Figur 63 er antallet af udvalgte knuder indtegnet som funktion af en fast defineret afstand til en fejlramt knude i et logaritmisk koordinatsystem. Det ses tydeligt, at udvælgelsen af knuder afhænger af den maksimale afstand disse knuder må befinde sig fra en fejlramt knude, og at denne afhængighed er eksponentiel. Et bedste fit er desuden indtegnet på Figur 63 for de første tre målepunkter.
Grunden til at målepunkterne synes at bøje af og det sidste målepunkt ikke er medtaget til beregning af et bedste fit er følgende: Udvælgelsen af knuder foregår vha. BFS og da grafen kun har en endelig størrelse, vil man når r vokser ”støde ind i kanten” af grafen, jævnfør Figur 61. Antallet af udvalgte knuder vokser altså eksponentielt, så længe man ikke rammer grafens ydre grænse. Derfor baseres generaliseringen kun på de første målepunkter.
Testdata viser desuden at W er cirka 32 af V allerede for r =4 i disse tilfældigt genererede grafer. Det maksimale antal kanter en udvalgt knude må ligge fra en afbrudt knude skal altså ikke være særlig højt, før man udvælger samtlige knuder i grafen.
Samtidig er det muligt at konstruere grafer, hvor dette ikke er tilfældet, eksempelvis vil et maskenet med store loops ikke have denne egenskab.
11.1.2 Afhængighed af grad
10 knuder tilfældigt til at være fejlmeldt. Resultatet kan ses på Figur 64. Det fuldstændige datasæt kan ses i Appendiks 4.
2 3 4 5 6
0 100 200 300 400 500 600 700 800 900 1000
grad
|W|
Figur 64: Antallet af udvalgte knuder som funktion af grafens grad.
Ud fra grafen på Figur 64 ser der ud til at være en lineær sammenhæng mellem antallet af udvalgte knuder og grafens grad. Denne sammenhæng kan forklares ud fra at antallet af naboer til én fejlmeldt knude stiger lineært med grafens grad.
11.1.3 Alternative forklaringer
I de to foregående afsnit har vi gennemgået hvilke faktorer der har indflydelse på antallet af udvalgte knuder, W . I dette afsnit vil vi undersøge hvordan antallet af alternative forklaringer afhænger af W .
Når et antal knuder er udvalgt til at danne basis for de alternative forklaringer, er det næste skridt at danne disse alternative forklaringer. Dette gøres ved at udregne alle permutationer af de udvalgte knuder og kombinere hver enkelt permutation med de fejlramte knuder. Hver enkelt af disse kombinationer danner basis for en ny forklaring.
Disse forklaringer evalueres i forhold til objektfunktionen, for at finde den bedste forklaring.
Vi generer et antal testgrafer, hver med 100 knuder og et gennemsnitligt antal kanter fra hver knude på to. Ved at vælge værdier for r og derefter vælge tre knuder tilfældigt der markeres som fejlmeldte, kan vi finde W . Knuderne i W benyttes nu sammen med
knuderne i F til at danne mængden af alternative forklaringer . Det fuldstændige datasæt kan ses i
Qr
Appendiks 5.
1 2 3 4
100 1050 10100 10150 10200 10250 10300
grad=2 grad=3 grad=4 grad=5 grad=6
r
log |Qr|
Figur 65: Logaritmen til antallet af alternative forklaringer som funktion af en fast defineret afstand til en fejlmeldt knude, r.
Figur 65 viser logaritmen til antallet af alternative forklaringer som funktion af r for grafer af forskellig grad. Antallet af alternative forklaringer er beregnet som samtlige permutationer af knuderne i W. Altså Qr =2W . Som grafen tydeligt viser, eksploderer antallet af alternative forklaringer når en højere værdi for r vælges, eksempelvis findes der ca. 67 mill. forklaringer for r =1, grad =3, blot i dette lille net. Dette er en meget uheldig egenskab ved BOMS.