Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Component evolution in random intersection graphs. | Component evolution in random intersection graphs Michael Behrisch Institut fur Informatik Humboldt-Universitat zu Berlin 10099 Berlin Germany behrisch@ Submitted Jan 21 2005 Accepted Oct 26 2006 Published Jan 29 2007 Mathematics Subject Classification 05C80 Abstract We study the evolution of the order of the largest component in the random intersection graph model which reflects some clustering properties of real-world networks. We show that for appropriate choice of the parameters random intersection graphs differ from Gn p in that neither the so-called giant component appearing when the expected vertex degree gets larger than one has linear order nor is the second largest of logarithmic order. We also describe a test of our result on a protein similarity network. 1 Introduction The classical random graph model introduced by Erdos and Rényi in the early 1960s considers a fixed set of n vertices and edges that exist with a certain probability p p n independently from each other. It was shown to be inappropriate for describing real-world networks because it lacks certain features of those . scale free degree distribution and clustering . One of the underlying reasons that are responsible for this mismatch is precisely the independence of the edges in other words the missing transitivity. In a real-world network relations between vertices x and y on the one hand and between vertices y and z on the other hand suggest a connection of some sort between vertices x and z. An intersection graph is a graph on vertex set V where each vertex has a subset of a ground set W assigned and two vertices are adjacent if and only if the assigned sets have a non-empty intersection. We call the ground set W from which the assigned sets are chosen universal feature set and its elements features. Furthermore the set of vertices Vw holding a specified feature w which obviously forms a clique is called feature clique while Wv shall denote the feature set assigned
