NDLI: An Algebraic Analysis of the Graph Modularity

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Fasino, Dario Tudisco, Francesco
Copyright Year	2014
Abstract	One of the most relevant tasks in network analysis is the detection of community structures, or clustering. Most popular techniques for community detection are based on the maximization of a quality function called modularity, which in turn is based upon particular quadratic forms associated to a real symmetric modularity matrix $M$, defined in terms of the adjacency matrix and a rank-one null model matrix. That matrix could be posed inside the set of relevant matrices involved in graph theory, alongside adjacency and Laplacian matrices. In this paper we analyze certain spectral properties of modularity matrices, which are related to the community detection problem. In particular, we propose a nodal domain theorem for the eigenvectors of $M$; we point out several relations occurring between the graph's communities and nonnegative eigenvalues of $M$; and we derive a Cheeger-type inequality for the graph modularity.
Starting Page	997
Ending Page	1018
Page Count	22
File Format	PDF
ISSN	08954798
DOI	10.1137/130943455
e-ISSN	10957162
Journal	SIAM Journal on Matrix Analysis and Applications (SJMAEL)
Issue Number	3
Volume Number	35
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2014-07-17
Access Restriction	Subscribed
Subject Keyword	Eigenvalues, singular values, and eigenvectors Factorization, matching, partitioning, covering and packing nodal domains Graphs and linear algebra graph partitioning graph modularity community detection spectral partitioning
Content Type	Text
Resource Type	Article
Subject	Analysis

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Community Detection in Networks via Nonlinear Modularity Eigenvectors

Edge-Connectivity, Eigenvalues, and Matchings in Regular Graphs

On the Quality of Spectral Separators

An algebraic analysis of the graph modularity

Graph Embeddings and Laplacian Eigenvalues

Eigenvectors of Distance-Regular Graphs

On spectral partitioning of signed graphs

Packing $k$-Matchings and $k$-Critical Graphs

Packings by Complete Bipartite Graphs

An Algebraic Analysis of the Graph Modularity

Similar Documents

Community Detection in Networks via Nonlinear Modularity Eigenvectors

Edge-Connectivity, Eigenvalues, and Matchings in Regular Graphs

On the Quality of Spectral Separators

An algebraic analysis of the graph modularity

Graph Embeddings and Laplacian Eigenvalues

Eigenvectors of Distance-Regular Graphs

On spectral partitioning of signed graphs

Packing $k$-Matchings and $k$-Critical Graphs

Packings by Complete Bipartite Graphs

An Algebraic Analysis of the Graph Modularity