AitF: Fast and Accurate Memristor-Based Algorithms for Social Network Analysis

Syracuse University, Syracuse NY

Investigators

Abstract

The area of computational social network analysis includes fundamental problems such as predicting the spread of information or disease, detecting communities in a population, and identifying missing links in an incomplete network. Common techniques for solving such problems require matrix-vector multiplications, a computationally-expensive mathematical operation. If performed at the software level, such multiplications can be prohibitively slow, particularly for the large-scale networks that are becoming increasingly prevalent in real applications. Instead, the PIs will perform these multiplications at the hardware level by using the memristor device, a newly invented chip component. In this project, the PIs will develop scalable, efficient, and effective memristor-based algorithms for problems in network analysis. Such algorithms will have a clear impact across scientific disciplines, as well as on tools used in practice. This project bridges the two areas of hardware and algorithms, and provides excellent topics for graduate student researchers, who the PIs will recruit from a diverse student body, including women and other underrepresented groups. Additionally, the research developed in this project will be incorporated into coursework taught by the PIs at Syracuse University. The project will investigate the use of memristors in developing effective, scalable algorithms for social network analysis, with potentially major effects both on research and practice. One can assemble memristors into a crossbar array, and by effectively setting and modifying the resistances of the memristors (which can be done in real-time), this array can represent a matrix. By applying proper voltages at the inputs of the array, one can perform extremely fast matrix-vector multiplication at the hardware level. The resistances can be set in parallel in O(N) time, and the matrix-vector multiplication itself can be done in O(1) time. Even for large matrices which must be partitioned to fit on the crossbar array hardware, one can expect running time reductions of multiple orders of magnitude, allowing for fast, potentially real-time, network analysis. The project will consider four major topics: (1) Eigenvalue and eigenvector finding, (2) Information spread in networks, (3) Pathfinding and prediction of missing links, and (4) Community detection. Using these topics as reference points, the PIs will develop a suite of algorithms, general techniques, and theoretical analyses with broad applicability both inside and outside of social network analysis. These devices can be potentially utilized for solving many critical problems and applications to achieve transformative accelerations in speed, enhancements in scalability, and reductions in computational complexity and power/energy consumption.