Message-ID: <2122328711.3889.1597132577980.JavaMail.confluence@wiki.cns.iu.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_3888_2111592994.1597132577980" ------=_Part_3888_2111592994.1597132577980 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html Indegree Distribution

# Indegree Distribution

###### Description
=20

The algorithm builds the histogram of the values of the indegree of all = nodes, which will be delivered in the two output files.

=20
###### Pros & Cons
=20

The network to analyze must be directed, otherwise there are no special = constraints.

=20
###### Applications
=20

Basic analysis tool, not particular for special disciplines or problems.=

=20
###### Implementation Detail= s
=20

The algorithm requires two inputs, the file where the edges of the netwo= rk are listed and the number of points one wishes to have in the binned dis= tribution described below. A first read-in of the inputfile will set the va= lues of the number of nodes and edges of the network. In the second read-in= the indegrees of all nodes will be calculated. Then the distribution is ca= lculated.
The program generates two output files, corresponding to two = different ways of partitioning the interval spanned by the values of indegr= ee. In the first output, the occurrence of any indegree value between the m= inimum and the maximum is estimated and divided by the number of nodes of t= he network, so to obtain the probability: the output displays all indegree = values in the interval with their probabilities.
The second output give= s the binned distribution, i.e. the interval spanned by the values= of indegree is divided into bins whose size grows while going to higher va= lues of the variable. The size of each bin is obtained by multiplying by a = fixed number the size of the previous bin. The program calculates the fract= ion of nodes whose indegree falls within each bin. Because of the different= sizes of the bins, these fractions must be divided by the respective bin s= ize, to have meaningful averages.
This technique is particularly suitab= le to study skewed distributions: the fact that the size of the bins grows = large for large indegree values compensates for the fact that not many node= s have high indegree values, so it suppresses the fluctuations that one wou= ld observe by using bins of equal size. On a double logarithmic scale, whic= h is very useful to determine the possible power law behavior of the distri= bution, the points of the latter will appear equally spaced on the x-axis.<= br> The program runs in a time O(m), m being the number of edges of the net= work.

=20
=20
=20
###### Acknowledgements
=20

The algorithm was implemented and documented by S. Fortunato, integrated= by S. Fortunato and W. Huang.

=20
###### References
=20

Bollobas, B. (2002) Modern Graph Theory. Springer Verlag, New York.

= =20

Albert, R., and Barabasi, A.-L. (2002) Statistical mechanics of complex networks. Review of Modern Phys= ics 74:47-97.

=20

Newman, M.E.J. (2003) Th= e structure and function of complex networks. SIAM Review 45:167-256.=20

Pastor-Satorras, R., Vespignani, A.(2002) Evolution and Structure of the= Internet. Cambridge University Press.

=20

Boccaletti, S., Latora, V., Moreno, Y.,Chavez, M., Hwang, D.-U.(2006) Complex networks: Structure and dynamics. Physics= Reports 424: 175-308.

=20