A Hybrid Adjacency and Time-Based Data Structure for Analysis of Temporal Networks
- Project Research
- 1-5 Chapters
- Abstract : Available
- Table of Content: Available
- Reference Style: APA
- Recommended for : Student Researchers
- NGN 3000
Background
Related Work I begin with background information on ways for representing temporal networks and data structures for storing (static) networks. I then discuss work related to this thesis, including the use of hybrid data structures and other types of temporal network data structures. 2.1 Static Network Representations Static networks are typically represented in one of 3 ways [41]: • Adjacency matrix : A two-dimensional matrix, Auv, stores edge information for source node u to destination node v in the uvth element of the matrix. • Adjacency list: A set of lists, one for each source node u. Each list contains a series of destination nodes v, if edge (u, v) exists. • Adjacency dictionary: A hash table keyed by source nodes u mapped to the set of destination nodes v, if edge (u, v) exists. The adjacency matrix is the traditional data structure for network representation due to, in part, its simple construction, but also its prominence in key aspects of network analysis, such as spectral graph theory. The values stored in adjacency 7 matrices are typically boolean in nature, with a value of ”1” representing an edge is present between two nodes, and a value of ”0” otherwise. However, adjacency matrices can be modified to hold additional information by storing numeric values instead, e.g. edge weights. Since an adjacency matrix stores a value for both present and missing edges, it has a memory complexity of O(n 2 ), where n is the number of nodes, and is therefore only appropriate for smaller networks. The adjacency list representation aims to improve upon this memory complexity by removing the need to store missing edge information. By storing edges as a set of list, adjacency lists improve the memory complexity to O(k), where k is the number of edges. However, this approach suffers from increased time complexity during common operations such as finding if an edge exists between nodes u and v due to the unsorted nature of its lists. The adjacency dictionary representation is a variant on the standard adjacency list, by storing the edges in a hashed set rather than a list. Edges presence in an adjacency dictionary can be determined in O(1) time, matching the adjacency matrix, while retaining the O(k) space complexity of the adjacency list. By using a hash table instead of a hashed set, additional edge information can be stored inside the adjacency dictionary as well.
Related Project Materials
ASSESSING THE EFFECTIVENESS OF SOCIAL MEDIA ENTREPRENEURSHIP IN OUR CONTEMPORARY BUSINESS SOCIETY
Abstract
The study examines the impact of social media on entrepreneurship development among users in Z...
THE INFLUENCE OF ENDSARS PROTEST ON POLITICAL INTEREST OF NIGERIAN YOUTHS
ABSTRACT
The project on the influence of endsars protest on political interest of Nigerian youths. The...
DESIGN AND IMPLEMENTATION OF RADIO CONTROLLED CAR LOCK WITH 5MIN IGNITION DEACTIVATION
Abstract
The rate of car theft nowadays according to daily crime analysis is on the increase. Manual key locks have prov...
MOTIVATION AS A CORRELATE ON STUDENTS EMBARKING ON BIOLOGY RELATED BUSINESS AFTER GRADUATION IN ANINRI LOCAL GOVERNMENT AREA ENUGU STATE
Background of the Study
Education is a process, which may be formal or informal, that enlightens, build...
ANALYSIS OF GOVERNMENT POLICY'S IMPACT ON ACADEMIC ACTIVITIES OF STUDENTS
BACKGROUND OF THE STUDY
It is the responsibility of government to develop and execute policies that wil...
ROLE OF ACCOUNTING CONCEPTS AND CONVENTION IN FINANCIAL REPORTING
STATEMENT OF THE PROBLEMS
The following problems are encountered in the process of communicating information.
...AN INTERVENTIONAL STUDY ON ADHERENCE AND BLOOD PRESSURE CONTROL IN A TERTIARY HEALTH FACILITY IN NORTH-WEST NIGERIA
ABSTRACT
The prevalence of hypertension in Sub-Saharan Africa has experienced a tremendous increase due to low awareness, treatment and c...
PUMP CAPACITY DETERMINATION FOR TWO-PHASE VERTICAL FLUID FLOW
Statement Of The Problem
It is important to accurately predict the pressure drop accross a production system. This has b...
THE EFFECT OF INFORMATION TECHNOLOGY SYSTEM ON THE GROWTH OF SMES IN NIGERIA
ABSTRACT
This study was carried out to examine the effect of information technology system...
GENDER ISSUES IN AGRICULTURE AND RURAL DEVELOPMENT IN NIGERIA: THE ROLE OF WOMEN
Background of the Study
The first and most important component of food security is the practice of environmentally susta...
