The connected components

 

3 The connected components

 

Molloy and Reed [1995] showed that for a random graph with vertices of degree i, where  are non-negative values which sum to 1, the giant component emerges when

So long as the maximum degree is less than   They also show that almost surely there is no giant component when and maximum degree less than

Here we compute Q for our graphs.

We are thus led to consider the value  which is a solution to

If

We first summarize the results here:

1.   When  the random graph a. s. has no giant component. When  there is almost surely a unique giant component.

2.   When   almost surely the second largest components have size  there is almost surely a component of size x.

3.     When  almost surely the second largest components are of sizeFor any  there is almost surely a component of size x.

4.    When  the second largest components are a. s. of size  The graph is almost surely not connected.

5.      When 0 <β< 1, the graph is almost surely connected.

6.      For β = β0 = 3.47875 ..., this is a very complicated case. It corresponds to the double jump of random graph G(n, p) with p = 1 n. For β = 1, there is a nontrivial probability for either cases that the graph is connected or disconnected.

7.    For  this case is complicated case. It corresponds to the double jump of random graph  with .

8.    For , there is a nontrivial probability for either cases that the graph is connected or disconnected.

We remark that for β > 8, Molloy and Reed’s result immediately implies that almost surely there is no giant component. When β ≤ 8, additional analysis is needed to deal with the degree constraints. We will prove in Theorem 4.2 that almost surely there is no giant component when

 In section 5, we will deal with the range  We will show theorem5.1 that almost surely there is a unique giant component when furthermore, we will determine the size of the second largest components within a constant factor.

Comments

Post a Comment

Popular posts from this blog

INTRODUCTION TO STATISTICS

 UNIT 1 INTRODUCTION TO STATISTICS Structure 1.0 Introduction 1.1 Objectives 1.2 Meaning of Statistics 1.2.1 Statistics in Singular Sense 1.2.2 Statistics in Plural Sense 1.2.3 Definition of Statistics 1.3 Types of Statistics 1.3.1 On the Basis of Function 1.3.2 On the Basis of Distribution of Data 1.4 Scope and Use of Statistics 1.5 Limitations of Statistics 1.6 Distrust and Misuse of Statistics 1.7 Let Us Sum Up 1.8 Unit End Questions 1.9 Glossary 1.10 Suggested Readings 1.0 INTRODUCTION The word statistics has different meaning to different persons. Knowledge of statistics is applicable in day to day life in different ways. In daily life it means general calculation of items, in railway statistics means the number of trains operating, number of passenger’s freight etc. and so on. Thus statistics is used by people to take decision about the problems on the basis of different type of quantitative and qualitative information available to them. However, in behavioural sciences, the ...
Read more

GRAPHICAL METHODS IN OPERATION RESEARCH

Image
  Linear Programming Linear programming is a mathematical technique employed to determine the most favorable solution for a problem characterized by linear relationships. It is a valuable tool in fields such as operations research, economics, and engineering, where efficient resource allocation and optimization are critical. Now let’s learn about types of linear programming problems Types of Linear Programming Problems There are mainly three types of problems based on Linear programming they are, Manufacturing Problem:  In this type of problem, some constraints like manpower, output units/hour, and machine hours are given in the form of a linear equation. And we have to find an optimal solution to make a maximum profit or minimum cost. Diet Problem:  These problems are generally easy to understand and have fewer variables. Our main objective in this kind of problem is to minimize the cost of diet and to keep a minimum amount of every constituent in the diet.  Transpo...
Read more

Difference between Batch Gradient Descent and Stochastic Gradient Descent

Image
  Difference between Batch Gradient Descent and Stochastic Gradient Descent In order to train a Linear Regression model, we have to learn some model parameters such as feature weights and bias terms. An approach to do the same is Gradient Descent which is an iterative optimization algorithm capable of tweaking the model parameters by minimizing the cost function over the train data. It is a complete algorithm i.e it is guaranteed to find the global minimum (optimal solution) given there is enough time and the learning rate is not very high. Two Important variants of Gradient Descent which are widely used in Linear Regression as well as Neural networks are Batch Gradient Descent and Stochastic Gradient Descent(SGD).  Batch Gradient Descent:  Batch Gradient Descent involves calculations over the full training set at each step as a result of which it is very slow on very large training data. Thus, it becomes very computationally expensive to do Batch GD. However, this is gre...
Read more