izpis_h1_title_alt

Vložitev vozlišč omrežja v linearni prostorski zahtevnosti
ID KOCIJAN, VID (Author), ID Demšar, Janez (Mentor) More about this mentor... This link opens in a new window, ID Leskovec, Jure (Co-mentor)

.pdfPDF - Presentation file, Download (1,08 MB)
MD5: E5DDA41AD93A585424D9EA5CA2E9AD13
PID: 20.500.12556/rul/842e86d9-1a41-4aa2-a2de-fca9c746b144

Abstract
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.

Language:Slovenian
Keywords:Vložitev vozlišč, omrežje, naključni sprehodi
Work type:Bachelor thesis/paper
Organization:FRI - Faculty of Computer and Information Science
Year:2017
PID:20.500.12556/RUL-94163 This link opens in a new window
Publication date in RUL:19.07.2017
Views:1098
Downloads:500
Metadata:XML RDF-CHPDL DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Secondary language

Language:English
Title:Vertex embeddings in linear space complexity
Abstract:
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.

Keywords:vertex embeddings, network, random walks

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back