File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Cheeger inequalities for general edge-weighted directed graphs

TitleCheeger inequalities for general edge-weighted directed graphs
Authors
Chan, HTHTang, ZZhang, C
Issue Date2015
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 21st Annual International Computing and Combinatorics Conference (COCOON 2015), Beijing, China, 4-6 August 2015. In Lecture Notes in Computer Science, 2015, v. 9198, p. 30-41 How to Cite?
DOI: http://dx.doi.org/10.1007/978-3-319-21398-9_3
AbstractWe consider Cheeger Inequalities for general edge-weighted directed graphs. Previously the directed case was considered by Chung for a probability transition matrix corresponding to a strongly connected graph with weights induced by a stationary distribution. An Eulerian property of these special weights reduces these instances to the undirected case, for which recent results on multi-way spectral partitioning and higher-order Cheeger Inequalities can be applied. We extend Chung’s approach to general directed graphs. In particular, we obtain higher-order Cheeger Inequalities for the following scenarios: (1) The underlying graph needs not be strongly connected. (2) The weights can deviate (slightly) from a stationary distribution.
DescriptionLNCS v.9188 entitled: Computing and Combinatorics: 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings
Persistent Identifierhttp://hdl.handle.net/10722/219231
ISSN
0302-9743
2023 SCImago Journal Rankings: 0.606
ISI Accession Number ID
WOS:000363954100003

 

DC FieldValueLanguage
dc.contributor.authorChan, HTH-
dc.contributor.authorTang, Z-
dc.contributor.authorZhang, C-
dc.date.accessioned2015-09-18T07:18:21Z-
dc.date.available2015-09-18T07:18:21Z-
dc.date.issued2015-
dc.identifier.citationThe 21st Annual International Computing and Combinatorics Conference (COCOON 2015), Beijing, China, 4-6 August 2015. In Lecture Notes in Computer Science, 2015, v. 9198, p. 30-41-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/219231-
dc.descriptionLNCS v.9188 entitled: Computing and Combinatorics: 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings-
dc.description.abstractWe consider Cheeger Inequalities for general edge-weighted directed graphs. Previously the directed case was considered by Chung for a probability transition matrix corresponding to a strongly connected graph with weights induced by a stationary distribution. An Eulerian property of these special weights reduces these instances to the undirected case, for which recent results on multi-way spectral partitioning and higher-order Cheeger Inequalities can be applied. We extend Chung’s approach to general directed graphs. In particular, we obtain higher-order Cheeger Inequalities for the following scenarios: (1) The underlying graph needs not be strongly connected. (2) The weights can deviate (slightly) from a stationary distribution.-
dc.languageeng-
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Science-
dc.rightsThe final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-21398-9_3-
dc.titleCheeger inequalities for general edge-weighted directed graphs-
dc.typeConference_Paper-
dc.identifier.emailChan, HTH: hubert@cs.hku.hk-
dc.identifier.authorityChan, HTH=rp01312-
dc.description.naturepostprint-
dc.identifier.doi10.1007/978-3-319-21398-9_3-
dc.identifier.scopuseid_2-s2.0-84951135189-
dc.identifier.hkuros254377-
dc.identifier.volume9198-
dc.identifier.spage30-
dc.identifier.epage41-
dc.identifier.isiWOS:000363954100003-
dc.publisher.placeGermany-
dc.customcontrol.immutablesml 151126; 160624 postprint added-
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats