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

计算社会网络分析的领域包括基本问题，如预测信息或疾病的传播，检测人群中的社区，以及识别不完整网络中的缺失链接。解决这类问题的常用技术需要矩阵-向量乘法，这是一种计算量很大的数学运算。如果在软件级别执行，这样的乘法可能会慢得令人望而却步，特别是对于在实际应用中变得越来越普遍的大规模网络。取而代之的是，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.