Vložitev vozlišč omrežja v linearni prostorski zahtevnosti

KOCIJAN, VID (avtor), Demšar, Janez (mentor), Leskovec, Jure (komentor)

Da bi za napovedovanje obnašanja omrežij lahko uporabili algoritme za strojno učenje, moramo vozlišča omrežja predstaviti kot vektorje v nizkodimenzional- nem vektorskem prostoru. Trenutno najučinkovitejši algoritem za računanje vložitve vozlišč omrežja v vektorski prostor je Node2vec, ki omrežje vzorči s pristranskimi naključnimi sprehodi drugega reda. Algoritem Node2vec ima žal visoko pomnilniško zahtevnost zaradi velike količine predpomnjenih tabel verjetnostnih porazdelitev, kar povprečnemu uporabniku onemogoči uporabo na večjih omrežjih. V tem diplomskem delu je predstavljen hevristični pri- stop k simulaciji naključnih sprehodov z binarnimi drevesi, ki zagotavlja line- arno časovno in pomnilniško zahtevnost simulacije, a hkrati ohranja kvaliteto izračunanih značilk. Hevristični pristop je na preizkušenih naborih podatkov porabil od 6-krat pa do 40-krat manj pomnilnika kot algoritem Node2vec.

• Jezik: Slovenski jezik
• Ključne besede: Vložitev vozlišč, omrežje, naključni sprehodi
• Vrsta gradiva: Diplomsko delo/naloga
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2017
• PID: 20.500.12556/RUL-94163
• Datum objave v RUL: 19.07.2017

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Vertex embeddings in linear space complexity

Izvleček

In order to predict the behaviour of networks with machine-learning algo- rithms, the vector representation of nodes in a low dimensional vector space is required. The current state-of-the-art algorithm for the calculation of node embeddings in vector space is Node2vec. Node2vec samples the network through the 2nd order random walks. Unfortunately, Node2vec has a high memory complexity due to the preprocessed probability-distribution tables. Due to high memory complexity, an average user is unable to use it for larger networks. In this thesis, we present a heuristic approach to the random walk simulation. The heuristic approach replaces probability tables with binary trees and guarantees linear time and space complexity, while retaining the quality of computed features. The heuristic approach requires from 6 up to 40 times less memory than Node2vec on tested datasets.

• Ključne besede: vertex embeddings, network, random walks