社会网络是社会科学与计算机科学的交叉研究方向。随着互联网的发展，以脸谱网、微博为代表的在线社交网络平台兴起，传统的以几十人为研究对象的社会网络分析研究让位于动辄成千上万个节点规模的在线社会网络。与传统社会网络类似，在线社会网络的基本研究单位也是一个社会图，可以用与传统社会网络分析类似的算法进行研究。然而，在线社会网络与传统社会网络在两个方面有非常大的不同：1）在线社会网络的规模非常巨大，其节点和链接数动辄数以百万计；2）在线社会网络的关联关系非常复杂，两个节点间的关系往往在数秒内发生变化。种种这些特点，需要有对传统社会网络分析的方法和算法进行发展以适应新的应用环境。社区发现算法大致分为以下几种：使用图分割方法将社会网络中的节点分到指定的几个社区，这种方式需要指定社区的数目和大小，而实际上这种情况往往不成立。层次聚类算法往往得到多个不同的解。模块函数方法需要的计算量非常大，不适合在当前线社会网络环境。由此，基于谱聚类算法，引入了一种正定谱聚类算法。谱聚类算法利用降维降低聚类的复杂度，且不需要事先制定分区的数目和大小。正定谱聚类算法则通过机器学习的方法挑选样本然后再降维进一步地降低了聚类的复杂度，使得算法更加适合于在线社会网络的环境。基于社会网络中的两点间距离的图构建方式是谱聚类和正定谱聚类算法的基础。这种图构建方式是整个算法的瓶颈部分，需要消耗大量的计算资源。同时这种构图方式不能适应基准的变化，且没有利用社会关系图中的整体信息。针对这些缺点，引入了一种称之为1-图的图构建方式，这种图构建是一种稀疏构建方式，适合于在线社会网络。另外，针对在线社会网络中大量存在的有向社会网络情况，介绍了一种基于随机游走的图拉普拉斯矩阵来进行处理。此外，通过对社会网络的链接预测问题的研究，将其抽象为一个二分类问题，可以使用机器学习的方式进行处理。在核投影机(Kernel Projection Machine,KPM)算法的基础上，提出了一种名为截断KPM算法的分类算法，给出了这个算法的表示定理并予以证明。同时，给出了截断KPM算法的两个收敛定理，并对这两个定理进行了证明。实验结果表明，截断KPM算法能在更宽的截断阈值范围内取得更高的预测精度。社会网络中存在着大量的未标记样本，如何有效地利用这些为标记样本也是一个重要研究点。通过研究已有的半监督学习算法，将一种名为自训练半监督算法的方法引入到截断KPM算法中来，提出了一种名为半监督截断KPM算法的半监督分类算法。在对比实验中，半监督截断KPM算法比KPM算法在预测精度上有了更大的提高，且预测结果能在有限的迭代次数内收敛，有效地利用了未标记样本。