{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T20:13:32Z","timestamp":1762460012436,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T00:00:00Z","timestamp":1622505600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T00:00:00Z","timestamp":1622505600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"INdAM-GNCS"},{"DOI":"10.13039\/100014810","name":"Fondazione di Sardegna","doi-asserted-by":"publisher","award":["research project \u201cAlgorithms for Approximation with Applications (Acube)\u201d"],"award-info":[{"award-number":["research project \u201cAlgorithms for Approximation with Applications (Acube)\u201d"]}],"id":[{"id":"10.13039\/100014810","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009873","name":"Regione Autonoma della Sardegna","doi-asserted-by":"publisher","award":["RASSR57257"],"award-info":[{"award-number":["RASSR57257"]}],"id":[{"id":"10.13039\/501100009873","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper introduces the notions of chained and semi-chained graphs. The chain of a graph, when existent, refines the notion of bipartivity and conveys important structural information. Also the notion of a center vertex <jats:inline-formula><jats:alternatives><jats:tex-math>$$v_c$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>v<\/mml:mi>\n                    <mml:mi>c<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is introduced. It is a vertex, whose sum of <jats:italic>p<\/jats:italic> powers of distances to all other vertices in the graph is minimal, where the distance between a pair of vertices <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\{v_c,v\\}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>{<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>v<\/mml:mi>\n                      <mml:mi>c<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>v<\/mml:mi>\n                    <mml:mo>}<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is measured by the minimal number of edges that have to be traversed to go from <jats:inline-formula><jats:alternatives><jats:tex-math>$$v_c$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>v<\/mml:mi>\n                    <mml:mi>c<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> to <jats:italic>v<\/jats:italic>. This concept extends the definition of closeness centrality. Applications in which the center node is important include information transmission and city planning. Algorithms for the identification of approximate central nodes are provided and computed examples are presented.<\/jats:p>","DOI":"10.1007\/s41109-021-00377-4","type":"journal-article","created":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T17:10:19Z","timestamp":1622567419000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Chained graphs and some applications"],"prefix":"10.1007","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2409-8466","authenticated-orcid":false,"given":"Anna","family":"Concas","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Lothar","family":"Reichel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Giuseppe","family":"Rodriguez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Yunzi","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,1]]},"reference":[{"key":"377_CR1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511984068","volume-title":"Bipartite graphs and their applications","author":"AS Asratian","year":"1998","unstructured":"Asratian AS, Denley TMJ, H\u00e4ggkvist R (1998) Bipartite graphs and their applications. Cambridge University Press, Cambridge"},{"key":"377_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-6569-9","volume-title":"Graphs and matrices","author":"RB Bapat","year":"2014","unstructured":"Bapat RB (2014) Graphs and matrices, 2nd edn. Springer, London","edition":"2"},{"key":"377_CR3","unstructured":"Batagelj V, Mrvar A (2006) Pajek data sets. http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/data\/"},{"key":"377_CR4","unstructured":"Biological Networks Data Sets of Newcastle University. http:\/\/www.biological-networks.org\/"},{"key":"377_CR5","doi-asserted-by":"publisher","first-page":"1170","DOI":"10.1086\/228631","volume":"92","author":"P Bonacich","year":"1987","unstructured":"Bonacich P (1987) Power and centrality: a family of measures. Am J Sociol 92:1170\u20131182","journal-title":"Am J Sociol"},{"key":"377_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph theory with applications","author":"JA Bondy","year":"1976","unstructured":"Bondy JA, Murty USR (1976) Graph theory with applications. MacMillan, London"},{"key":"377_CR7","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.socnet.2004.11.008","volume":"27","author":"SP Borgatti","year":"2005","unstructured":"Borgatti SP (2005) Centrality and network flow. Soc Netw 27:55\u201371","journal-title":"Soc Netw"},{"key":"377_CR8","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.ins.2014.02.040","volume":"275","author":"L Chen","year":"2014","unstructured":"Chen L, Yu Q, Chen B (2014) Anti-modularity and anti-community detecting in complex networks. Inf Sci 275:293\u2013313","journal-title":"Inf Sci"},{"key":"377_CR9","doi-asserted-by":"crossref","unstructured":"Concas A, Noschese S, Reichel L, Rodriguez G (2020) A spectral method for bipartizing a network and detecting a large anti-community. J Comput Appl Math 373, Art. 112306","DOI":"10.1016\/j.cam.2019.06.022"},{"key":"377_CR10","unstructured":"Delicious. http:\/\/www.delicious.com"},{"key":"377_CR11","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199591756.001.0001","volume-title":"The structure of complex networks: theory and applications","author":"E Estrada","year":"2011","unstructured":"Estrada E (2011a) The structure of complex networks: theory and applications. Oxford University Press, Oxford"},{"key":"377_CR12","doi-asserted-by":"crossref","unstructured":"Estrada E (2011b) Community detection based on network communicability. Chaos 21, Art. 016103","DOI":"10.1063\/1.3552144"},{"key":"377_CR13","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1137\/090761070","volume":"52","author":"E Estrada","year":"2010","unstructured":"Estrada E, Higham DJ (2010) Network properties revealed through matrix functions. SIAM Rev 52:696\u2013714","journal-title":"SIAM Rev"},{"key":"377_CR14","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.physd.2015.10.020","volume":"323\u2013324","author":"E Estrada","year":"2016","unstructured":"Estrada E, G\u00f3mez-Garde\u00f1es J (2016) Network bipartivity and the transportation efficiency of European passenger airlines. Physica D 323\u2013324:57\u201363","journal-title":"Physica D"},{"key":"377_CR15","volume-title":"A first course in network theory","author":"E Estrada","year":"2015","unstructured":"Estrada E, Knight P (2015) A first course in network theory. Oxford University Press, Oxford"},{"key":"377_CR16","doi-asserted-by":"crossref","unstructured":"Estrada E, Rodriguez-Velazquez JA (2005) Subgraph centrality in complex networks. Phys Rev 71, Art. 056103","DOI":"10.1103\/PhysRevE.71.056103"},{"key":"377_CR17","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1016\/j.laa.2017.12.001","volume":"542","author":"D Fasino","year":"2017","unstructured":"Fasino D, Tudisco F (2017) A modularity based spectral method for simultaneous community and anti-community detection. Linear Algebra Appl 542:605\u2013623","journal-title":"Linear Algebra Appl"},{"key":"377_CR18","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"S Fortunato","year":"2010","unstructured":"Fortunato S (2010) Community detection in graphs. Phys Rep 486:75\u2013174","journal-title":"Phys Rep"},{"key":"377_CR19","unstructured":"Gleich D. MatlabBGL\u2014A Matlab Graph Library. https:\/\/www.cs.purdue.edu\/homes\/dgleich\/packages\/matlab_bgl\/"},{"key":"377_CR20","first-page":"192","volume-title":"Social informatics. SocInfo 2013. Lecture Notes in Computer Science","author":"K Ikematsu","year":"2013","unstructured":"Ikematsu K, Murata T (2013) A fast method for detecting communities from tripartite networks. In: Jatowt A et al (eds) Social informatics. SocInfo 2013. Lecture Notes in Computer Science, vol 8238. Springer, Cham, pp 192\u2013205"},{"key":"377_CR21","volume-title":"Graph coloring problems","author":"TR Jensen","year":"1995","unstructured":"Jensen TR, Toft B (1995) Graph coloring problems. Wiley, New York"},{"key":"377_CR22","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1038\/35075138","volume":"411","author":"H Jeong","year":"2001","unstructured":"Jeong H, Mason S, Barab\u00e1si A-L, Oltvai ZN (2001) Lethality and centrality of protein networks. Nature 411:41\u201342","journal-title":"Nature"},{"key":"377_CR23","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1038\/nphys1746","volume":"11","author":"M Kitsak","year":"2010","unstructured":"Kitsak M, Gallos LK, Havlin S, Liljeros F, Muchnik L, Stanley HE, Makse HA (2010) Identification of influential spreaders in complex networks. Nat Phys 11:888\u2013893","journal-title":"Nat Phys"},{"key":"377_CR24","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D K\u00f6nig","year":"1916","unstructured":"K\u00f6nig D (1916) \u00dcber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math Ann 77:453\u2013465","journal-title":"Math Ann"},{"key":"377_CR25","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: an introduction","author":"MEJ Newman","year":"2010","unstructured":"Newman MEJ (2010) Networks: an introduction. Oxford University Press, Oxford"},{"key":"377_CR26","unstructured":"Page L, Brin S, Motwani R, Winograd T (1999) The PageRank citation ranking: bringing order to the web, Technical Report, Stanford InfoLab"},{"key":"377_CR27","doi-asserted-by":"crossref","unstructured":"Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76, Art. 036106","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"377_CR28","doi-asserted-by":"publisher","first-page":"2443","DOI":"10.1093\/nar\/gkg340","volume":"31","author":"S Sun","year":"2003","unstructured":"Sun S, Ling L, Zhang N, Li G, Chen R (2003) Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic Acids Res 31:2443\u20132450","journal-title":"Nucleic Acids Res"},{"key":"377_CR29","unstructured":"U.S. Department of Transportation. Consumer Airfare Report: Table 1 Top 1,000 Contiguous State City-Pair Markets"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00377-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-021-00377-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-021-00377-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T17:54:05Z","timestamp":1622570045000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-021-00377-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,1]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["377"],"URL":"https:\/\/doi.org\/10.1007\/s41109-021-00377-4","relation":{},"ISSN":["2364-8228"],"issn-type":[{"type":"electronic","value":"2364-8228"}],"subject":[],"published":{"date-parts":[[2021,6,1]]},"assertion":[{"value":"3 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"39"}}