DANF: Approximate Neighborhood Function on Large Dynamic Graphs Continuously finding changes in node centrality

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/237805
Download file(s):
File Description SizeFormat 
237805.pdfFulltext794.48 kBAdobe PDFView/Open
Full metadata record
DC FieldValueLanguage
dc.contributor.authorLINDHÈN, SIMON
dc.contributor.authorHANSEN, JOHAN NILSSON
dc.contributor.departmentChalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)sv
dc.contributor.departmentChalmers University of Technology / Department of Computer Science and Engineering (Chalmers)en
dc.date.accessioned2019-07-03T13:54:46Z-
dc.date.available2019-07-03T13:54:46Z-
dc.date.issued2016
dc.identifier.urihttps://hdl.handle.net/20.500.12380/237805-
dc.description.abstractThe neighborhood function measures node centrality in graphs by measuring how many nodes a given node can reach in a certain number of steps. The neighborhood function can for example be used to find central nodes or the degree of separation. The state-of-the-art algorithm, called HyperANF (Hyper Approximate Neighborhood Function), can calculate an approximate neighborhood function for graphs with billions of nodes within hours using a standard workstation [P. Boldi, M. Rosa, and S. Vigna, “Hyperanf: Approximating the neighbourhood function of very large graphs on a budget,” CoRR, vol. abs/1011.5599, 2010]. However, it only supports static graphs. If the neighborhood function should be calculated on a dynamic graph, the algorithm has to be re-run at any change in the graph. We develop a novel algorithm called Dynamic Approximate Neighborhood Function (DANF) which extends HyperANF to support dynamic graphs. In our algorithm, all relevant nodes are updated when new edges are added to the graph. This allows a constantly updated neighborhood function for all nodes in large graphs. DANF will be used on a real-time data stream supplied by the company Meltwater, where about 2 million news articles are received per day. Rapidly changing nodes and trends are detected by tracking the nodes whose centrality change by an insertion. This is used to monitor which subjects are getting more or less popular.
dc.language.isoeng
dc.setspec.uppsokTechnology
dc.subjectData- och informationsvetenskap
dc.subjectComputer and Information Science
dc.titleDANF: Approximate Neighborhood Function on Large Dynamic Graphs Continuously finding changes in node centrality
dc.type.degreeExamensarbete för masterexamensv
dc.type.degreeMaster Thesisen
dc.type.uppsokH
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.