图论作为组合数学的一个重要分支,从18世纪的柯尼斯堡(Konigsberg)“七桥问题”开始,已经有很长的研究历史。近几年,随着复杂网络和“大数据科学”的崛起,图与网络的研究受到了越来越多的关注。在大数据背景下,图与网络存在于社会生活的各个方面,例如Facebook、微信中的朋友关系可以用一般网络来表示,生物系统中基因间的促进与抑制关系可以用符号网络结构来刻画,在药物组合研究中,超图得到了广泛的应用等。另外,随着数据挖掘、收集、整理技术的进步,对于图与网络的研究从静态结构逐步拓展到动态结构,对数据内部复杂关系进行了更加精准的刻画。不同类型的图与网络结构在刻画数据内在关系时具有不同的侧重点和优势,本文分别对几种不同的网络类型进行描述,并针对几个重点问题展开研究。本文共分为六章。第一章为绪论,简单介绍了目前图与网络方向的几个重点关注问题,并介绍了几种网络类型。第二章至第五章为文章的主体部分,也是本文的主要创新点。第六章中我们首先对所做工作进行总结,并在这些工作的基础上,做了进一步的研究计划和展望。首先,针对符号网络(Signed Networks)的结构特征,我们提出了一种新的随机游走模型,并对该随机游走模型的主要性质进行研究。符号网络中存在两种不同的边,即正边和负边。基于这两种边,符号网络可以分为正层网络和负层网络。在经典的随机游走或者动力学研究中,边是动力学过程的主要“媒介”,会促进信息、病毒等的传播。而符号网络中正边和负边具有不同的性质,例如可以分别代表社会关系中的朋友和敌人关系,基因调控网络中的促进和抑制关系等,在动力学过程中必然会展现出不同的功能。我们以商品网络为例,正边表示商品间的互补关系、负边表示商品间的可替代或竞争关系。我们规定在随机游走过程中,游走者在正边游走,负边对网络进行修剪,且游走者不能重复访问已被访问过的节点。我们称这种随机游走为自回避修剪随机游走(Self-avoiding Pruning Random Walk(SAP walk))。我们针对该随机游走的三种主要性质进行研究:修剪后网络结构的演化,主要是正层网络平均度的变化;随机游走长度,即每次随机游走可访问的正边数量或者节点数量;节点的访问概率,即给定节点的初始正度,该节点在每次随机游走过程中被访问的概率。对以上三种性质我们进行了理论分析和数值模拟,并且分别研究了网络的度分布、度-度相关性、社团结构等对随机游走的影响。该游走过程的提出为推荐系统的构建提供了新的思路,如何设计合理的推荐网络使长期推荐利益最大化是一个值得长期研究的问题。其次,针对符号网络中的结构平衡理论(Structure Balance Theory),我们提出了一种基于条件概率的符号网络生成模型,并利用该模型研究了网络的结构平衡性对SAP walk的影响。结构平衡性是符号网络的重要性质之一,在本文中,我们将其定义为平衡三角形占总三角形的比例。大多数真实符号网络都表现出很强的结构平衡性,对网络中平衡结构生成过程的研究是符号网络研究的重要课题。符号网络的生成模型与一般网络的生成模型有很大的差异,以三角形为例,无向符号网络中的三角形存在四种形态,而平衡三角形的比例很高,如何在生成网络的过程中控制平衡三角形的比例是符号网络模型设计的重点和难点。我们基于条件概率设计了一种简单的符号网络生成模型,其思想是首先生成无符号网络结构,然后对不含三角形的子网络中的边进行随机安排符号,最后基于条件概率对剩余边安排符号。另外,我们对模型的主要性质进行了理论分析,并且基于该模型,我们研究了网络的结构平衡性对SAP walk的影响,我们发现网络的平衡结构有利于SAP walk,即相对而言网络的平衡性越高,网络被修剪速度越慢,随机游走长度越长,节点的访问概率越高。该工作为商业领域中商品的推广提供了新的思路,以商品网络为例,相同的商品,在更平衡的推荐网络中能够得到更好的推广。再次,针对染色网络或者染色图,我们研究了染色图上的彩色匹配问题。给定一个n个顶点的图G,并且图G的边集可以分解为m个s-因子。Alspach提出如下问题:当s = 2时,是否存在m条边的匹配M,使得每条边来自一个2-因子?这种匹配在设计理论中应用广泛,称之为正交匹配(Orthogonal Matchings)。如果每个s-因子用一种颜色来染,那么就构成一个染色图,上述问题转化为染色图上的彩色匹配问题。我们证明了当n≤2.83m时该结论成立。目前该结果是最好的。染色图在大数据环境下受到了越来越多的关注,例如,我们把来自不同数据库的蛋白质相互作用网络看作一个边染色图,每种颜色表示一种数据库,这样就构成了一个边染色重图。我们研究边染色图的结构和性质以及应用性强的子图的存在性问题,这些问题的解决能使我们更有效地利用各种数据来深入分析网络结构,对于预测蛋白质功能、寻找药物靶点等方面的应用都有非常重要的推动作用。最后,针对时序网络数据(Temporal Networks),我们研究了时序网络中的节点重要性问题。节点重要性问题是复杂网络领域中长期研究的重要问题,其在静态网络中的研究已经比较成熟,但是时序网络中的节点重要性指标比较缺失,研究难度也大大提高。时序网络与静态网络最大的不同在于时间维度的引入,在这种情况下,网络结构随时间是不断变化的,节点的重要性随时间也是变化的。如何在时序网络中更好的刻画节点的整体重要性是我们研究的主要问题,而不是在某个时刻的节点重要性。我们提出一种基于信息收集的节点重要性框架,在此框架下,网络中每个节点都包含初始信息,例如一个研究组中的新成员最初进入小组时与其他成员没有交流,其重要性或属性只能通过其初始属性来衡量。随着时间的演化,其重要性不断变化,可以用其邻域内节点来估计。基于这一框架,我们可以设计一种时序网络上的节点重要性指标,也可以利用该框架研究时间因素对网络中节点排序的影响。该工作为探索时间因素在大数据环境下对网络结构、功能等影响的相关研究提供了新的工具和思路。