近年来,随着Web2.0等互联网新概念的日益付诸实践,社交网络作为其中一种新兴的,实用的交友模式,依赖其真实性,稳定性等特点得到了用户的青睐,在网络活动中发挥着越来越重要的作用。我们可以看到,很多社交网站在最近几年取得了巨大的成就,例如Myspace已经成为全美最受欢迎的网站之一,统计表明其流量相当于Internet总流量的4.46%;Yahoo的图片分享及社交网络结合体Flickr,已经拥有超过400万用户和2亿上传图片;而作为全美第二大的社交网站Facebook,在创立的短短三年之内,市值就已达到了惊人的150亿美元;在国内方面,“校内网”作为大学生最主要的交流平台,也已经拥有超过2200万真实注册用户。社交网络是指建立在真实人际关系基础上的网络平台,是作为现实中的社会团体在互联网上交流的辅助工具而存在。社交网络是现实活动的在线拓展,与传统的虚拟网络有很大的不同。传统虚拟网络脱离社会现实,结构相对无序、混乱,而社交网络作为现实人际网络的子集,同样具有人际网络的一些特征,正是基于如此,我们认为对社交网络进行一定的研究是可行的,这对于促进社交网络的进一步发展具有重要的理论意义。本文以社交网络为平台,以计算机图论知识为基础,对人际关系做了深入的研究和分析。在此基础上提出了基于星状子图结构的社交网络社区识别算法,该算法利用社交网络中包含有大量星状子图的结构特点对现有的识别算法进行改进,极大地提高了算法的识别效率。另外,本篇论文还引入了用户影响力评估系统UserRank,这是在社交网络领域首次尝试利用网络结构对用户影响力进行评估。该系统认为社交网络的人际结构决定了用户的影响力,通过对人际结构的分析和计算可以对用户影响力进行恰当的评估。模型的验证是以“校内网”为平台,通过计算网络上所有浙大用户的影响力,并同实际情况进行比较分析,有力的证明了UserRank评价系统的准确性和可行性。