Many real life complex networks consists of a tremendous amount of nodes and edges which make them difficult to extract and analyze. This thesis aims to examine what network prop- erties that can be deduced when considering small samples of a complex network and how well they correspond to the characteristics of the complete network. This is of importance as sampling will most likely be the de facto method when analyzing complex networks in the future. The study examine the scale-free property, the small-world property and the com- munity structure of the network spanned by the KTH domain. The method consisted of gathering data about the network through sampling it in a breadth-first manner using a web crawler. The samples was then compared with respect to each property. The results was that good approximations of the scale-free property could be made from small samples of the KTH network. However, no good approximation could be made about the small-world property using the sampling technique. Good approximations about a node’s community affiliation could be observed. However, general conclusions of the com- plete network’s community structures could not be made. To summarize, the result indi- cate that small samples can be used to approximate some properties of the complete KTH network. However, to determine if the result is true for the general case more research is necessary. / Komplexa nätverk i vår omvärld består av ett stort antal hörn och kanter vilket gör dem svå- ra att extrahera och analysera. Denna rapport undersöker vilka nätverksegenskaper som kan härledas vid undersökningen av små stickprov av ett nätverk och hur bra dessa representerar egenskaperna hos det fullständiga nätverket. Detta är av betydelse eftersom användandet av små stickprov kommer troligtvis att vara standarden vid undersökningar av nätverk i framtiden. Denna studie undersökte scale-free egenskapen, small-world egenskapen och community strukturen för nätverket som omfattas av KTH domaänen. Metoden innefattade att samla in data om nätverket genom stickprov baserat på en bredden-först sökning. Detta realiserades genom att använda en sökrobot. Sedan jämfördes de olika stickproven med avseende på de olika nätverksegenskaperna. Resultetat visade att nätverkets scale-free egenskap kunde approximaeras med små stickprov. Däremot var det inte möjligt att approximera nätverkets small-world egenskap genom användet av den givna stickprovsmetoden. Goda approximationer observerades för att avgöra ett hörns community tillhörighet men den allmäna community strukturen kunde inte approximeras. Sammanfattningsvis visade resultatet att stickprov kan användas för att approximera vissa egenskaper hos det fullständiga KTH nätverket men att mer forskning krävs för att avgöra om resultaten kan generaliseras.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-208346 |
| Date | January 2017 |
| Creators | Westlund, Johannes, Svenningsson, Jakob |
| Publisher | KTH, Skolan för datavetenskap och kommunikation (CSC) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0103 seconds