随着信息技术的迅速发展,网络成为数据的重要来源。图上信号作为网络上数据的数学抽象,受到了越来越多的关注,图上信号处理成为近年来信号处理领域的研究热点之一。采样是信号处理的基本问题,目前针对图上信号采样问题的研究并不完善,仍处于发展阶段。本文主要针对图上信号的采样与重建问题展开研究,具体包括图上信号采样重建算法、时变图上信号的分布式跟踪以及图上信号采样的拓展,此外还研究了有向图的平衡性度量问题,本文的主要创新点如下:1.研究利用采样值重建原图上信号的算法,提出两种基于局部节点集的迭代重建算法,证明当图上信号的截止频率满足一定条件时,所提出的算法可唯一精确重建原带限图上信号。给出框架理论在图上信号处理问题中的表现形式,建立图上信号采样重建问题与时域非规则采样问题的对应关系。实验表明,相比已有迭代重建算法,所提出算法的收敛速度得到了显著提升。2.研究时变图上信号的分布式跟踪算法,利用时变信号的采样值分布式地跟踪原信号的变化,给出满足收敛条件所需的步长参数,可自适应地对时变信号进行增量式更新。本研究将图上信号的采样与重建问题拓展到时变、分布式场景。实验表明,所提出分布式算法可正确跟踪随时间缓变的图上信号。3.研究图上信号的广义采样与重建问题,提出基于局部观测的广义采样方式,提出利用局部观测值重建原信号的迭代算法并给出理论分析,给出噪声干扰下算法的性能分析。本研究对图上信号的传统抽取式采样进行一般化,拓展了图上信号采样问题的研究范围和研究思路。实验表明,基于局部观测的广义采样方式具有更强的抗噪声性能。4.研究有向图平衡性的度量方法,提出边平衡度、正向系数的概念度量有向边及全图的平衡性,给出入度服从幂律分布、出边无偏的有向图边平衡度分布的理论结果。同时对Twitter和新浪微博等真实在线社交网络数据集进行实验验证,发现真实社交网络的结构特征。