Structure And Dynamic Process In Graphs And Networks

Graph theory,as an important,branch of combinatorial mathematics,has a long research history,starting from the Seven Bridges of Konigsberg in the 18th century.In recent years,with the rise of complex networks and"Big Data" science,the research on graphs and networks has received more and more attentions.In the "Big Data" time,graphs and networks exist,in many aspects of the social life.For example,friends relationship in Face-book and WeChat,can be represented by general networks.The relationship between genes,i.e.,promotion and inhibition in biological systems can be characterized by signed networks.The hyper-graph structure has been wide-ly used in the study of drug combination.Recently,with the advancement of techniques in data mining and data collection,the research on graphs and networks has gradually expanded from static organizations to dynamic ones,which can be applied on mapping data into networks more vividly.Different types of graphs and networks have different focuses and ad-vantages on portraying data inter-relationships.This work describes several different types of networks and studies several key research problems.This thesis is divided into six chapters.The first chapter is an introduction.We introduces several key issues of current,graphs and networks,and introduces several types of networks briefly.The second chapter to the fifth chapter are the main part of this work,which is also the main innovation of this article.In the sixth chapter,we first summarize what we have done and on the basis of these results,we make further research plan and prospects.Firstly.we propose a new random walk model based on the structural characteristics of signed networks and study the main properties of the ran-dom walk process.There are two different types of links in signed networks,namely the positive links and the negative links.Based on these two kind-s of links,the network can be divided into a positive layer and a negative layer.In the general random walk or dynamic process,the edge is the main"media" of the process,which will promote the spreading of information.viruses and so on.In the signed network,the positive and negative links have different properties,such as friends and enemies in social networks,the promotion and inhibition relationship in gene regulatory networks.Differ-ent functions are inevitably exhibited in the dynamic process.Taking the commodity network as an example,the positive link indicates the comple-mentary relationship between commodities and the negative link indicates the alternative or competitive relationship between commodities.Then in the random walk,the walker walks on positive links and negative links prune the network,which can be used to describe the users purchase behavior.We define this random walk as a self-avoiding pruning random walk(SAP walk).We study the three main properties of the random walk:the evolution of the network structure after pruning,namely the changing of the average positive degree;the random walk length,that is,the number of positive links can be visited for each random walk;the visiting probability of each node with the given initial positive degree,i.e.,the probability that the node will be visit-ed during each random walk.We have carried out theoretical analysis and numerical simulations on the above three properties and studied the impact of degree distribution of the network,the degree-degree correlation,and the community structure on the random walk properties.The proposal of SAP walk provides a new sight for the construction of the recommendation sys-tem.How to design the recommendation network to maximize the long-term recommendation is a long-term research problem.Secondly,we propose a signed network model based on conditional prob-ability.And we use this model to study the impact of structural balance onSAP walk.Structural balance is one of the most important properties of signed networks.In this study,we define it as the ratio of balanced trian-gles to total number of triangles.Most real-world signed networks exhibit strong structural balance.Research on the generation process of balance structure is one of the most important problems on signed network research.The generation model of signed networks is very different from that of general networks.Taking the triangle as an example,there are four types of triangles in an undirected signed network,and the proportion of balanced triangles is very high.How to control the proportion of balanced triangles is a difficult point in the design of signed network models.We design a simple signed network model based on the conditional probability.The idea is to first gen-erate an unsigned network structure,then randomly assign the edges in the subnetwork without triangles.Finally,assign each remaining links based on the conditional probability.In addition,we theoretically analyse the main properties of the model.Based on the model,we study the influence of the structural balance on SAP walk.We find that the balanced structure is ben-eficial to SAP walk,that is,the more balanced the network is,the slower the network being pruned,the longer the random walk length and the higher probability the node being visited.This work provides a new way to better promote some certain products in the commercial field.Taking the commod-ity network as an example,the same products can be better promoted in a more balanced recommendation network.Thereafter,we introduce a generalized network model of signed net-works,namely colored networks or colored graphs.We study the rainbow matching problem on colored graphs.Given a graph G of n vertices,and the edge set of the graph G can be decomposed into m s-factors.Alspach asked the following question:when s= 2,is there a matching M of m links,so that each edge is chosen from a 2-factor?This kind of matching is widely used in design theory and is called orthogonal matchings.If each s-factor is colored with a single color,then a colored graph is formed and the above problem is transformed into a rainbow matching problem on the colored graph.We prove that,the question mentioned above is true when n≤2.83m.The re-sult is the best until now.Colored graphs have received increasing attentions in the big data field.For example,we consider the protein interaction net-works from different,databases as different,colors.Each color represents a database,which constitutes an edge colored graph.We study the structure and properties of edge-colored graphs and the existence of various theoreti-cal and applied subgraphs.The solution of these problems enables us to use various data more effectively to analyse the network structure deeply.It is very important to the study on predicting protein functions and detecting drug targets.Finally,we study the node ranking problem in temporal networks.Node importance is an important topic in the field of complex networks.Its re-search in static networks is relatively mature,but the study of node ranking methods in the temporal network is relatively lacking.As the consideration of temporal information,the research is much more difficult than that in static networks.The biggest difference between temporal networks and static ones is the introduction of time dimension.Thus,the network structure changes continuously with time and the importance of nodes changes with time as well.How to better describe nodes’ importance is the main point of our re-search,instead of the importance of the node at some time slot.We propose a node importance framework based on information gathering.Under this framework,each node in the network is given a piece of initial information.For example,a new member of a research group does not communicate with other members when it first enters the group.Initially,her/his importance can only be measured by her/this initial attributes.As time going,her/his importance changes and can be measured by users within the neighborhood.Based on this framework,we can design a node importance measurement and the framework can also be used to study the influence of temporal informa-tion on node ranking.This work provides new tools and ideas for exploring the influence of temporal information on the network structure or network functions in the big data field.