近年来,随着互联网的迅速发展,以及智能手机、平板电脑、笔记本电脑的日益普及,在线社交网络（Online Social Networks,OSNs）已经成为了人们日常生活中获取新闻资讯、交友互动、传播信息、视频通信、娱乐放松的重要渠道之一。在计算机科学、社会学、管理学、心理研究、人类行为研究科学等学科的研究与应用领域内,在线社交网络已成为一个热门话题。由于在线社交网络会随时间、人类行为的变化而变化,导致其具有结构复杂性、群体性以及信息的快速传播性、数量增长性等特点。因此,在线社交网络用户的个体性行为、交友互动、创建内容、信息传播和群体集会等行为的频繁发生,对国家的信息安全、经济发展、社会稳定、政治健康等方面都有深远的影响。在线社交网络应用的蓬勃发展,受到了各领域学者的广泛关注。在计算机科学领域,利用各种计算机数据分析方法研究在线社交网络的工作层出不穷。本学位论文将利用图论和形式概念分析方法,来研究在线社交网络的极大派系（Maximal Clique）检测和演化分析。极大派系挖掘问题是图数据挖掘中的一个非常重要的研究课题,这个研究最关键的一点是如何从图数据中迅速识别出极大派系。由于针对的是在线社交网络中的极大派系挖掘和检测问题,一定要考虑到在线社交网络的复杂性、多变性等特点。为此,本论文采用形式概念分析（Formal Concept Analysis,FCA）理论,将在线社交网络的极大派系挖掘问题转换对在线社交网络对应的概念格的分析。本论文设计了两种概念格生成算法:Add-FCA和Dec-FCA,分别适用于在线社交网络中当用户增加或减少时的极大派系检测,该算法的特点在于无需重新对用户发生变化的在线社交网络进行形式背景构造,而是利用已有的概念格获取新的概念格,从而进一步省时、有效地检测极大派系,刻画在线社交网络中极大派系的演化过程。在本论文中,给出了所提算法的正确性证明,且通过实验验证了算法的高效性。在检测极大派系的过程中,利用等势概念（Equiconcept）与极大派系的等价性,研究等势概念的演化,发现了极大派系的四种演化方式:不变的极大派系（Unchanged Maximal Clique,UE）、改变的极大派系（Changed Maximal Clique,CE）、新增的极大派系（Added Maximal Clique,AE）,消亡的极大派系（Vanished Maximal Clique,VE）。并且通过多次实验,研究实验数据增中的等势概念数量和极大派系数量,找出了这四种极大派系与改变前后的在线社交网络的极大派系数量之间的恒等关系。此外,本学位论文提出的Add-FCA算法和Dec-FCA算法不仅可以适用于在线社交网络,同样可以适用于一般的形式背景的对象/属性改变时概格的生成。本论文的主要贡献有:1.设计了两个适用于动态改变的形式背景的概念格生成算法:Add-FCA和Dec-FCA算法。其中,Add-FCA是对象或属性动态增加的形式背景的概念格生成算法,Dec-FCA是对象或属性动态减少的形式背景的概念格生成算法。本论文给出了算法的具体步骤和数学化正确性证明,并进行了实验测试其正确性和高效性;2.将图挖掘问题和研究概念格的问题结合起来,设计了新的极大派系检测算法:利用极大派系和等势概念的等价关系,将在线社交网络中检测极大派系的问题,转换为检测在线社交网络对应概念格的等势概念的问题。3.将极大派系的演化过程进行了分类,分成了 4类不同的极大派系演化类型（上述UE,CE,AE,VE）,并推出了这4类极大派系与初始极大派系之间的数量关系。