Modularity of networks

Skerman, F

Abstract:: Modularity is a quality function on partitions of a network which may be used to identify highly clustered components. It is commonly used to analyse large real networks, for example in social networks and protein discovery to find communities and related proteins respectively. Given a graph G, the modularity of a partition of the vertex set measures the extent to which edge density is higher within parts than between parts, and the maximum modularity q^*(G
Expand abstract
Collapse abstract

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Cite

Cite this record

APA Style

Skerman, F. (2015). Modularity of networks [PhD thesis]. University of Oxford.

MLA Style

Skerman, F. Modularity of Networks. University of Oxford, 2015.

Chicago Style

Skerman, F. 2015. “Modularity of Networks.” PhD thesis, University of Oxford.
Share
Print

Access Document

Files:: SkermanThesisFinal2.pdf

(Preview, pdf, 2.9MB, Terms of use)

Authors

+ Skerman, F More by this author

Division:: MPLS
Department:: Statistics
Role:: Author

Contributors

+ McDiarmid, C

Role:: Supervisor

DOI:: 10.5287/ora-z56gx5pd9
Type of award:: DPhil
Level of award:: Doctoral
Awarding institution:: University of Oxford

UUID:: uuid:1bbaaac7-bad0-469d-add4-6a0dbf75f7c6
Deposit date:: 2017-05-05

Related item:: Modularity of treelike and random regular graphs
Description:: Clustering algorithms for large networks typically use modularity values to test which partitions better represent structure in the data. We establish baselines for statistical tests on regular graphs, by showing that: for random cubic graphs the (maximum) modularity is usually in the interval (0.666, 0.804), and for random r-regular graphs with large r it usually is of order 1/√r. The modularity of cycles and low degree trees is known to be close to 1: we extend this to ‘treelike’ graphs, where the product of treewidth and maximum degree is much less than the number of edges.
Related item:: Modularity in random regular graphs and lattices
Description:: Given a graph G, the modularity of a partition of the vertex set measures the extent to which edge density is higher within parts than between parts; and the modularity of G is the maximum modularity of a partition. We give an upper bound on the modularity of r-regular graphs as a function of the edge expansion (or isoperimetric number) under the restriction that each part in our partition has a sub-linear numbers of vertices. This leads to results for random r-regular graphs. In particular we show the modularity of a random cubic graph partitioned into sub-linear parts is almost surely in the interval (0.66, 0.88). The modularity of a complete rectangular section of the integer lattice in a fixed dimension was estimated in Guimer et. al. [R. Guimerà, M. Sales-Pardo and L.A. Amaral, Modularity from fluctuations in random graphs and complex networks, Phys. Rev. E 70 (2) (2004) 025101]. We extend this result to any subgraph of such a lattice, and indeed to more general graphs.
Related item:: Modularity of Erdös-Rényi graphs near criticality
Related item:: Modularity of lattices and well-embeddable graphs

Terms of use

Copyright holder:: Skerman, F

Licence:: Terms and Conditions of Use for Oxford University Research Archive

Views and Downloads

About views and downloads

If you are the owner of this record, you can report an update to it here: Report update to this record

Thesis

Modularity of networks

Actions

Access Document

Authors

Contributors

Terms of use

Views and Downloads

Altmetrics

Dimensions

Thesis

Modularity of networks

Actions

Access Document

Authors

Contributors

Bibliographic Details

Item Description

Related Items

Terms of use

Metrics

Views and Downloads

Altmetrics

Dimensions