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

计算社会网络分析领域包括一些基本问题，如预测信息或疾病的传播，检测群体中的社区，以及识别不完整网络中的缺失链接。 解决这类问题的常用技术需要矩阵向量乘法，这是一种计算量很大的数学运算。 如果在软件级别执行，则这种乘法可能非常慢，特别是对于在真实的应用中变得越来越普遍的大规模网络。 相反，PI将通过使用忆阻器设备（一种新发明的芯片组件）在硬件级别执行这些乘法。 在这个项目中，PI将为网络分析中的问题开发可扩展的，高效的，有效的基于忆阻器的算法。 这种算法将对各个科学学科以及实践中使用的工具产生明显的影响。 该项目连接了硬件和算法这两个领域，并为研究生研究人员提供了优秀的课题，PI将从包括女性和其他代表性不足的群体在内的多元化学生中招募研究生。 此外，在这个项目中开发的研究将被纳入锡拉丘兹大学PI教授的课程。 该项目将研究忆阻器在开发有效的、可扩展的社交网络分析算法中的应用，对研究和实践都有潜在的重大影响。 人们可以将忆阻器组装成交叉阵列，并且通过有效地设置和修改忆阻器的电阻（这可以实时完成），该阵列可以表示矩阵。通过在阵列的输入端施加适当的电压，可以在硬件级别执行极快的矩阵向量乘法。 这两个电阻可以在O（N）时间内并行设置，而矩阵向量乘法本身可以在O（1）时间内完成。 即使对于必须划分以适合交叉开关阵列硬件的大型矩阵，也可以预期运行时间减少多个数量级，从而允许快速，潜在的实时网络分析。 该项目将考虑四个主要主题：（1）特征值和特征向量查找，（2）网络中的信息传播，（3）路径查找和缺失链接预测，以及（4）社区检测。 使用这些主题作为参考点，PI将开发一套算法，通用技术和理论分析，在社交网络分析内外都具有广泛的适用性。 这些设备可以潜在地用于解决许多关键问题和应用，以实现速度的变革性加速、可扩展性的增强以及计算复杂性和功耗/能耗的降低。

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.