Különböző alakzatokon alapuló skálafüggetlen véletlen hálózatok

Abstract

Ezen értekezésben először definiáljuk az csillagos véletlen gráf modellt, amely fejlődésében nagy szerepet játszik a preferential attachment szabály. A kialakuló gráfokat vizsgáljuk martingálelméleti módszerekkel, így a gráf ki- és befokának, illetve a gráf fejlődésekor használt súlyoknak a skálafüggetlenségét igazoljuk. Ezek után ismertetünk egy általános populációs modellt, ami az egyedek pontértéke alapján fejlődik. Ebben az esetben megmutatjuk, hogy a pontértékek skálafüggetlen tulajdonsággal rendelkeznek, ehhez koncentrációs egyenlőtlenséget használunk. Majd alkalmazzuk a kapott eredményeket a csillagos modellre és az N-pontos modellre. Végezetül szimulációs eredmények segítségével megmutatjuk, hogy az általánosított N-pontos modell esetén hatványrendű fokszámeloszlástól eltérőt kaphatunk, annak ellenére, hogy ez a modell is preferential attachment alapján fejlődik. In this dissertation, first we define the N-star random graph model, in which the preferential attachment rule plays a major role during the evolution. The obtained graphs are examined by martingale theory methods, so we prove the scale-free property of the out- and indegrees of the graph and the weights used during the evolution. Furthermore we present a general population model that evolves based on the scores of individuals. In this case, we show that the scores have a scale-free property, using concentration inequality. We apply the results to the N-star model and the N-interaction model. Finally, with the help of simulations, we show that in the case of the generalized N-interaction model we can get non-power-law distribution, despite the fact that this model also evolves on the basis of preferential attachment rule.