Type of Document Master's Thesis Author Parikh, Nidhi Kiranbhai Author's Email Address nidhip@vt.edu URN etd-03312011-224622 Title Generating Random Graphs with Tunable Clustering Coefficient Degree Master of Science Department Computer Science Advisory Committee

Advisor Name Title Heath, Lenwood S. Committee Chair Marathe, Madhav V. Committee Member Vullikanti, Anil Kumar S. Committee Member Keywords

- Clustering coefficient
- complex networks
- random graphs
- algorithms
Date of Defense 2011-03-18 Availability unrestricted AbstractMost real-world networks exhibit a high clustering coefficientâ€”the probability that two neighborsof a node are also neighbors of each other. We propose four algorithms CONF-1, CONF-2,

THROW-1, and THROW-2 which are based on the configuration model and that take triangle degree

sequence (representing the number of triangles/corners at a node) and single-edge degree sequence

(representing the number of single-edges/stubs at a node) as input and generate a random graph

with a tunable clustering coefficient. We analyze them theoretically and empirically for the case of

a regular graph. CONF-1 and CONF-2 generate a random graph with the degree sequence and the

clustering coefficient anticipated from the input triangle and single-edge degree sequences. At each

time step, CONF-1 chooses each node for creating triangles or single edges with the same probability,

while CONF-2 chooses a node for creating triangles or single edge with a probability proportional

to their number of unconnected corners or unconnected stubs, respectively. Experimental results

match quite well with the anticipated clustering coefficient except for highly dense graphs, in which

case the experimental clustering coefficient is higher than the anticipated value. THROW-2 chooses

three distinct nodes for creating triangles and two distinct nodes for creating single edges, while

they need not be distinct for THROW-1. For THROW-1 and THROW-2, the degree sequence and the

clustering coefficient of the generated graph varies from the input. However, the expected degree

distribution, and the clustering coefficient of the generated graph can also be predicted using analytical

results. Experiments show that, for THROW-1 and THROW-2, the results match quite well with

the analytical results. Typically, only information about degree sequence or degree distribution is

available. We also propose an algorithm DEG that takes degree sequence and clustering coefficient

as input and generates a graph with the same properties. Experiments show results for DEG that

are quite similar to those for CONF-1 and CONF-2.

Files

Filename Size Approximate Download Time (Hours:Minutes:Seconds)

28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access Parikh_NK_T_2011.pdf593.44 Kb 00:02:44 00:01:24 00:01:14 00:00:37 00:00:03

Browse All Available ETDs by
( Author |
Department )

If you have questions or technical problems, please Contact DLA.