{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T12:17:56Z","timestamp":1783685876057,"version":"3.55.0"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"Nation Key R&D Program of China","award":["2022YFA1005102"],"award-info":[{"award-number":["2022YFA1005102"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12526521"],"award-info":[{"award-number":["12526521"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12325112"],"award-info":[{"award-number":["12325112"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12288101"],"award-info":[{"award-number":["12288101"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2026,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Conventional spectral digraph partitioning methods typically symmetrize the adjacency matrix, thereby transforming the directed graph partitioning problem into an undirected one, where bipartitioning is commonly linked to minimizing graph conductance. However, such symmetrization approaches disregard the directional dependencies of edges in digraphs, failing to capture the inherent imbalance crucial to directed network modeling. Building on the parallels between digraph conductance and conductance under submodular transformations, we develop a generalized framework to derive their continuous formulations. By leveraging properties of the Lov\u00e1sz extension, this framework addresses the fundamental asymmetry problem in digraph partitioning. We then formulate an equivalent fractional programming problem, relax it via a three-step Dinkelbach iteration procedure, and design the Directed Simple Iterative ([Formula: see text]) algorithm for estimating digraph conductance. The subproblem within [Formula: see text] is analytically solvable, and the algorithm is guaranteed to converge provably to a binary local optimum. Extensive experiments on synthetic and real-world networks demonstrate that our [Formula: see text] algorithm significantly outperforms several state-of-the-art methods in digraph conductance minimization.<\/jats:p>","DOI":"10.1137\/25m1772393","type":"journal-article","created":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T11:29:32Z","timestamp":1783682972000},"page":"1166-1185","source":"Crossref","is-referenced-by-count":0,"title":["Conductance Estimation in Digraphs: Submodular Transformation, Lov\u00e1sz Extension, and Dinkelbach Iteration"],"prefix":"10.1137","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7439-9163","authenticated-orcid":true,"given":"Sihong","family":"Shao","sequence":"first","affiliation":[{"name":"CAPT, LMAM and School of Mathematical Sciences, Peking University, Beijing 100871, China."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chuan","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Fuzhou University, Fuzhou 350108, China, and School of Mathematical Sciences, Peking University, Beijing 100871, China."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xinyang","family":"Ye","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Peking University, Beijing 100871, China."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,7,10]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"L. A. Adamic and N. Glance, The political blogosphere and the 2004 U.S. election: Divided they blog, in Proceedings of the 3rd International ACM Workshop on Link Discovery (LinkKDD), 2005, pp. 36\u201343.","DOI":"10.1145\/1134271.1134277"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"R. Andersen, F. Chung, and K. Lang, Local graph partitioning using PageRank vectors, in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 475\u2013486.","DOI":"10.1109\/FOCS.2006.44"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1561\/2200000039"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1145\/2492007.2492029"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1126\/science.aad9029"},{"key":"ref6","unstructured":"A. Bovet and P. Grindrod, The Activity of the Far Right on Telegram, https:\/\/www.researchgate.net\/publication\/346968575_The_Activity_of_the_Far_Right_on_Telegram_v21, 2020."},{"key":"ref7","unstructured":"T. B\u00fchler, S. S. Rangapuram, S. Setzer, and M. Hein, Constrained fractional set programs and their application in local clustering and community detection, in Proceedings of the 30th International Conference on Machine Learning (ICML),\u00a02013, pp. 624\u2013632."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.4208\/jcm.1506-m2014-0164"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.4310\/CMS.2021.v19.n3.a9"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-005-0237-z"},{"key":"ref11","unstructured":"M. Cucuringu, H. Li, H. Sun, and L. Zanetti, Hermitian matrices for clustering directed graphs: Insights and applications, in Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108, 2020, pp. 983\u2013992."},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.13.7.492"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1126\/science.1136800"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.0020095"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"L. C. Lau, K. C. Tung, and R. Wang, Cheeger inequalities for directed graphs and hypergraphs using reweighted eigenvalues, in Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023, pp. 1834\u20131847.","DOI":"10.1145\/3564246.3585139"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"L. C. Lau, K. C. Tung, and R. Wang, Fast algorithms for directed graph partitioning using flows and reweighted eigenvalues, in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2024, pp. 591\u2013624, https:\/\/doi.org\/10.1137\/1.9781611977912.22.","DOI":"10.1137\/1.9781611977912.22"},{"key":"ref18","unstructured":"J. Leskove and A. Krevl, SNAP Datasets: Stanford Large Network Dataset Collection, http:\/\/snap.stanford.edu\/data, 2014."},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-68874-4_10"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnae016"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"V. Satuluri and S. Parthasarathy, Symmetrizations for clustering directed graphs, in Proceedings of the 14th International ACM Conference on Extending Database Technology, 2011, pp. 343\u2013354.","DOI":"10.1145\/1951365.1951407"},{"key":"ref23","unstructured":"S. Shao and C. Yang, A simple inverse power method for balanced graph cut, preprint, arXiv:2405.18705, 2024."},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.4310\/CMS.250208222749"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.4208\/jcm.2303-m2021-0309"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"H. Yin, A. R. Benson, J. Leskovec, and D. F. Gleich, Local higher-order graph clustering, in Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2017, pp. 555\u2013564.","DOI":"10.1145\/3097983.3098069"},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"Y. Yoshida, Nonlinear Laplacian for digraphs and its applications to network analysis, in Proceedings of the Ninth ACM International Conference on Web Search and Data Mining (WSDM), 2016, pp. 483\u2013492.","DOI":"10.1145\/2835776.2835785"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"Y. Yoshida, Cheeger inequalities for submodular transformations, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2019, pp. 2582\u20132601, https:\/\/doi.org\/10.1137\/1.9781611975482.160.","DOI":"10.1137\/1.9781611975482.160"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T11:29:36Z","timestamp":1783682976000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M1772393"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,10]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9,30]]}},"alternative-id":["10.1137\/25M1772393"],"URL":"https:\/\/doi.org\/10.1137\/25m1772393","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,10]]}}}