给定一个图G,边分类指利用G中有标签的边来给无标签的边加标签的问题。边分类问题在图挖掘和社会网络分析中有着广泛的应用,如关系发现、关系分类和关系推荐等。本文针对在大图中基于邻居相似性的边分类问题进行研究,研究内容如下:首先,通过深入分析现有方法,发现现有边分类算法在确定边(u,v)的标签时,通过计算u与邻居集合S(u)中顶点的相似性和v与邻居集合S(v)中顶点的相似性来推断边(u,v)的标签。这种方式需要判断相似顶点对的次数是|S(u)|*|S(v)|,实际应用中存在效果差,效率低的问题。其次,提出一种在线动态局部索引,可以降低图遍历的次数,从而提升求解效率。针对已有方法需要多次遍历图才能得到结果的问题,在第一次遍历图的过程中,记录已经求得的边的标签信息,在后续判断相似度最高的边时,无需对数据图再次遍历,直接通过索引求解。同时减少计算相似性顶点的数量,降低求解时遍历图的次数,提升求解效率。再次,针对上述方法存在效果差的问题,提出利用u的邻居和v计算相似性得到相似度最高的顶点w1,同时利用v的邻居和u计算相似性得到相似度最高的顶点w2。假设w1与v的相似性高于w2与u的相似性,则用w1与u之间边的标签来表示边(u,v)的标签。这种求解边分类问题的思路可以避免已有方法无法给部分边贴标签的问题,同时提出基于以上思路的高效算法BNSCA来求解边标签,同样将原方法判断顶点对相似性的次数从|S(u)|*|S(v)|减低到|S(u)|+|S(v)|。最后,在实验阶段,基于3个真实数据集。从计算相似顶点的时间,对无标签边贴上标签的准确率等方面进行了比较,验证了本文所提方法的高效性与准确性。