C programming challenge
Task
Write a C program, which needs a filename as a command line argument. This name specifies a file containing a graph. The program has to
calculate the average clustering coefficient of the graph and it have to print the value to the screen. The size of the graph is not fixed.
The program should be able to handle huge (millions of nodes) graphs as fast as possible.
Definitions
Neighbor
Nodes i and j are neighbors, if there is a direct edge between them.
Degree
The k
i degree of node i is the number of its neighbors.
Clustering coefficient
The C
i clustering coefficient of node i means the probability that the neighbors of i are also the neighbors of each other.
Thus you have to count the number of edges between the neighbors of i and then divide this number by the value of
k
i*(k
i-1)/2. (So C
i is a real number between 0 and 1.) The clustering coefficient is not defined for
nodes having less than 2 neighbors.
Average clustering coefficient
The average clustering coefficient (ACC) of a graph is the average of the clustering coefficients of all the node having at least 2
neighbors. (This it is the mean value of defined C
i values, a real number between 0 and 1.)
Input
The graph is represented in a text file, where the lines of the file contain node ID pairs describing edges (in the "%d\t%d\n" form,
so the last line can be empty). Node IDs are not negative integers (a kind of serial number started by 0). The order of edges in the file
is arbitrary, thus the file is not always sorted. The two integers in a line (representing an edge) are also not sorted. In the given
sample file some nodes have thousands of neighbors, while most of them have only a few (these are scale-free networks).
The graph is undirected and maximum 1 edge exists between two given nodes, what is more, no loop and no isolated nodes/subgraphs in the graph.
Submission
If your program provides correct results for these samples send the source code, your name and your Neputn ID to me.
Literature:
