{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T22:37:09Z","timestamp":1740177429214,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,10,27]],"date-time":"2020-10-27T00:00:00Z","timestamp":1603756800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,10,27]],"date-time":"2020-10-27T00:00:00Z","timestamp":1603756800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001871","name":"Fund\u00e7\u00f1o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["PD\/BD\/128160\/2016"],"award-info":[{"award-number":["PD\/BD\/128160\/2016"]}],"id":[{"id":"10.13039\/501100001871","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":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The hypergraph-of-entity is a joint representation model for terms, entities and their relations, used as an indexing approach in entity-oriented search. In this work, we characterize the structure of the hypergraph, from a microscopic and macroscopic scale, as well as over time with an increasing number of documents. We use a random walk based approach to estimate shortest distances and node sampling to estimate clustering coefficients. We also propose the calculation of a general mixed hypergraph density measure based on the corresponding bipartite mixed graph. We analyze these statistics for the hypergraph-of-entity, finding that hyperedge-based node degrees are distributed as a power law, while node-based node degrees and hyperedge cardinalities are log-normally distributed. We also find that most statistics tend to converge after an initial period of accentuated growth in the number of documents. We then repeat the analysis over three extensions\u2014materialized through<jats:italic>synonym<\/jats:italic>,<jats:italic>context<\/jats:italic>, and<jats:italic>tf_bin<\/jats:italic>hyperedges\u2014in order to assess their structural impact in the hypergraph. Finally, we focus on the application-specific aspects of the hypergraph-of-entity, in the domain of information retrieval. We analyze the correlation between the retrieval effectiveness and the structural features of the representation model, proposing ranking and anomaly indicators, as useful guides for modifying or extending the hypergraph-of-entity.<\/jats:p>","DOI":"10.1007\/s41109-020-00320-z","type":"journal-article","created":{"date-parts":[[2020,10,27]],"date-time":"2020-10-27T08:03:00Z","timestamp":1603785780000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Characterizing the hypergraph-of-entity and the structural impact of its extensions"],"prefix":"10.1007","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2780-2719","authenticated-orcid":false,"given":"Jos\u00e9","family":"Devezas","sequence":"first","affiliation":[]},{"given":"S\u00e9rgio","family":"Nunes","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,10,27]]},"reference":[{"key":"320_CR1","doi-asserted-by":"publisher","first-page":"0205497","DOI":"10.1371\/journal.pone.0205497","volume":"13","author":"D Aparicio","year":"2018","unstructured":"Aparicio D, Ribeiro P, Silva F (2018) Graphlet-orbit transitions (GOT): a fingerprint for temporal network comparison. PLoS ONE 13:0205497. https:\/\/doi.org\/10.1371\/journal.pone.0205497","journal-title":"PLoS ONE"},{"key":"320_CR2","doi-asserted-by":"publisher","unstructured":"Arvola P, Geva S, Kamps J, Schenkel R, Trotman A, Vainio J (2010) Overview of the INEX 2010 ad hoc track. In: Comparative evaluation of focused retrieval\u20149th international workshop of the inititative for the evaluation of XML retrieval, INEX 2010, Vugh, The Netherlands, 13\u201315 December 2010, Revised Selected Papers, pp 1\u201332. https:\/\/doi.org\/10.1007\/978-3-642-23577-1_1","DOI":"10.1007\/978-3-642-23577-1_1"},{"key":"320_CR3","volume-title":"Optimal traversal of directed hypergraphs","author":"G Ausiello","year":"1992","unstructured":"Ausiello G, Giaccio R, Italiano GF, Nanni U (1992) Optimal traversal of directed hypergraphs. ICSI, Berkeley, CA"},{"key":"320_CR4","doi-asserted-by":"crossref","unstructured":"Backstrom L, Boldi P, Rosa M, Ugander J, Vigna S (2011) Four degrees of separation. CoRR arXiv:1111.4570","DOI":"10.1145\/2380718.2380723"},{"key":"320_CR5","doi-asserted-by":"publisher","unstructured":"Backstrom L, Boldi P, Rosa M, Ugander J, Vigna S (2012) Four degrees of separation. In: Web science 2012, WebSci \u201912, Evanston, IL, USA\u201422\u201324 June 2012, pp 33\u201342. https:\/\/doi.org\/10.1145\/2380718.2380723","DOI":"10.1145\/2380718.2380723"},{"key":"320_CR6","unstructured":"Banerjee A, Char A (2017) On the spectrum of directed uniform and non-uniform hypergraphs. arXiv preprint arXiv:1710.06367"},{"issue":"2\u20133","key":"320_CR7","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1561\/1500000032","volume":"10","author":"H Bast","year":"2016","unstructured":"Bast H, Buchhold B, Haussmann E et al (2016) Semantic search on text and knowledge bases. Found Trends\u00ae Inf Retriev 10(2\u20133):119\u2013271","journal-title":"Found Trends\u00ae Inf Retriev"},{"key":"320_CR8","doi-asserted-by":"publisher","unstructured":"Bast H, Buchhold B (2013) An index for efficient semantic full-text search. In: Proceedings of the 22nd ACM international conference on conference on information and knowledge management, pp 369\u2013378. https:\/\/doi.org\/10.1145\/2505515.2505689","DOI":"10.1145\/2505515.2505689"},{"key":"320_CR9","doi-asserted-by":"crossref","unstructured":"Bastian M, Heymann S, Jacomy M (2009) Gephi: an open source software for exploring and manipulating networks. In: Proceedings of the third international conference on weblogs and social media, ICWSM 2009, San Jose, CA, USA, 17\u201320 May 2009. http:\/\/aaai.org\/ocs\/index.php\/ICWSM\/09\/paper\/view\/154","DOI":"10.1609\/icwsm.v3i1.13937"},{"key":"320_CR10","unstructured":"Berge C (1970) Graphes et Hypergraphes. Monographies universitaires de mathematiques. Dunod, Paris"},{"key":"320_CR11","doi-asserted-by":"crossref","unstructured":"Bhagdev R, Chapman S, Ciravegna F, Lanfranchi V, Petrelli D (2008) Hybrid search: effectively combining keywords and semantic searches. In: European semantic web conference. Springer, pp 554\u2013568","DOI":"10.1007\/978-3-540-68234-9_41"},{"key":"320_CR12","doi-asserted-by":"crossref","unstructured":"Brandes U, Eiglsperger M, Herman I, Himsolt M, Marshall MS (2001) Graphml progress report structural layer proposal. In: International symposium on graph drawing. Springer, pp 501\u2013512","DOI":"10.1007\/3-540-45848-4_59"},{"key":"320_CR13","unstructured":"Brown W, Erdos P, S\u00f3s V (1973) Some extremal problems on r-graphs. In: New directions in the theory of graphs (Proceedings third Ann Arbor Conference, University Michigan, Ann Arbor, MI, 1971), pp 53\u201363"},{"issue":"5","key":"320_CR14","first-page":"1","volume":"1695","author":"G Csardi","year":"2006","unstructured":"Csardi G, Nepusz T et al (2006) The igraph software package for complex network research. InterJ Compl Syst 1695(5):1\u20139","journal-title":"InterJ Compl Syst"},{"issue":"1","key":"320_CR15","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1515\/comp-2019-0006","volume":"9","author":"J Devezas","year":"2019","unstructured":"Devezas J, Nunes S (2019) Hypergraph-of-entity: a unified representation model for the retrieval of text and knowledge. Open Comput Sci 9(1):103\u2013127. https:\/\/doi.org\/10.1515\/comp-2019-0006","journal-title":"Open Comput Sci"},{"key":"320_CR16","doi-asserted-by":"publisher","unstructured":"Devezas JL, Nunes S (2019) Characterizing the hypergraph-of-entity representation model. In: Complex networks and their applications VIII\u2014volume 2 proceedings of the eighth international conference on complex networks and their applications COMPLEX NETWORKS 2019, Lisbon, Portugal, 10\u201312 Dec 2019, pp 3\u201314. https:\/\/doi.org\/10.1007\/978-3-030-36683-4_1","DOI":"10.1007\/978-3-030-36683-4_1"},{"issue":"1","key":"320_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0012-365X(71)90002-1","volume":"1","author":"P Erd\u00f6s","year":"1971","unstructured":"Erd\u00f6s P (1971) On some extremal problems on r-graphs. Discrete Math 1(1):1\u20136. https:\/\/doi.org\/10.1016\/0012-365X(71)90002-1","journal-title":"Discrete Math"},{"key":"320_CR18","doi-asserted-by":"publisher","first-page":"106","DOI":"10.4153\/CJM-1966-014-3","volume":"18","author":"P Erd\u00f6s","year":"1966","unstructured":"Erd\u00f6s P, Goodman AW, P\u00f3sa L (1966) The representation of a graph by set intersections. Can J Math 18:106\u2013112","journal-title":"Can J Math"},{"key":"320_CR19","unstructured":"Estrada E, Rodriguez-Velazquez JA (2005) Complex networks as hypergraphs. arXiv preprint arXiv:0505137 [physics]"},{"key":"320_CR20","first-page":"1","volume":"1","author":"JD Fern\u00e1ndez","year":"2016","unstructured":"Fern\u00e1ndez JD, Mart\u00ednez-Prieto MA, de la Fuente Redondo P, Guti\u00e9rrez C (2016) Characterizing RDF datasets. J Inf Sci 1:1\u201327","journal-title":"J Inf Sci"},{"key":"320_CR21","doi-asserted-by":"publisher","unstructured":"Gallagher SR, Goldberg DS (2013) Clustering coefficients in protein interaction hypernetworks. In: ACM conference on bioinformatics, computational biology and biomedical informatics. ACM-BCB 2013, Washington, DC, USA, 22\u201325 Sept 2013, p 552. https:\/\/doi.org\/10.1145\/2506583.2506635","DOI":"10.1145\/2506583.2506635"},{"issue":"2","key":"320_CR22","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0166-218X(93)90045-P","volume":"42","author":"G Gallo","year":"1993","unstructured":"Gallo G, Longo G, Pallottino S (1993) Directed hypergraphs and applications. Discrete Appl Math 42(2):177\u2013201. https:\/\/doi.org\/10.1016\/0166-218X(93)90045-P","journal-title":"Discrete Appl Math"},{"issue":"6","key":"320_CR23","doi-asserted-by":"publisher","first-page":"1805","DOI":"10.1109\/TNET.2014.2343914","volume":"23","author":"J Gao","year":"2015","unstructured":"Gao J, Zhao Q, Ren W, Swami A, Ramanathan R, Bar-Noy A (2015) Dynamic shortest path algorithms for hypergraphs. IEEE\/ACM Trans Netw 23(6):1805\u20131817. https:\/\/doi.org\/10.1109\/TNET.2014.2343914","journal-title":"IEEE\/ACM Trans Netw"},{"key":"320_CR24","doi-asserted-by":"publisher","unstructured":"Ge W, Chen J, Hu W, Qu Y (2010) Object link structure in the semantic web. In: The semantic web: research and applications, 7th extended semantic web conference, ESWC 2010, Heraklion, Crete, Greece, 30 May\u20133 June 2010, proceedings, part II, pp 257\u2013271. https:\/\/doi.org\/10.1007\/978-3-642-13489-0_18","DOI":"10.1007\/978-3-642-13489-0_18"},{"issue":"1\u20132","key":"320_CR25","doi-asserted-by":"publisher","first-page":"7","DOI":"10.2478\/v10248-012-0011-5","volume":"17","author":"M G\u0142\u0105bowski","year":"2012","unstructured":"G\u0142\u0105bowski M, Musznicki B, Nowak P, Zwierzykowski P (2012) Shortest path problem solving based on ant colony optimization metaheuristic. Image Process Commun 17(1\u20132):7\u201317","journal-title":"Image Process Commun"},{"key":"320_CR26","unstructured":"Halpin H (2009) A query-driven characterization of linked data. In: Proceedings of the WWW2009 workshop on linked data on the web, LDOW 2009, Madrid, Spain, 20 April 2009"},{"key":"320_CR27","unstructured":"Himsolt M (1997) GML: a portable graph file format. Technical report, Universit\u00e4t Passau"},{"key":"320_CR28","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1000385","author":"S Klamt","year":"2009","unstructured":"Klamt S, Haus U, Theis FJ (2009) Hypergraphs and cellular networks. PLoS Comput Biol. https:\/\/doi.org\/10.1371\/journal.pcbi.1000385","journal-title":"PLoS Comput Biol"},{"key":"320_CR29","unstructured":"Li D (2011) Shortest paths through a reinforced random walk. Technical report, University of Uppsala"},{"key":"320_CR30","unstructured":"Mikolov T, Sutskever I, Chen K, Corrado GS, Dean J (2013) Distributed representations of words and phrases and their compositionality. In: Advances in neural information processing systems 26: 27th annual conference on neural information processing systems 2013. Proceedings of a Meeting Held 5\u20138, 2013, Lake Tahoe, Nevada, USA, pp 3111\u20133119. http:\/\/papers.nips.cc\/paper\/5021-distributed-representations-of-words-and-phrases-and-their-compositionality"},{"issue":"1","key":"320_CR31","first-page":"60","volume":"2","author":"S Milgram","year":"1967","unstructured":"Milgram S (1967) The small world problem. Psychol Today 2(1):60\u201367","journal-title":"Psychol Today"},{"issue":"11","key":"320_CR32","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/219717.219748","volume":"38","author":"GA Miller","year":"1995","unstructured":"Miller GA (1995) Wordnet: a lexical database for english. Commun ACM 38(11):39\u201341. https:\/\/doi.org\/10.1145\/219717.219748","journal-title":"Commun ACM"},{"issue":"6","key":"320_CR33","doi-asserted-by":"publisher","first-page":"1118","DOI":"10.1016\/j.jcta.2006.11.006","volume":"114","author":"D Mubayi","year":"2007","unstructured":"Mubayi D, Zhao Y (2007) Co-degree density of hypergraphs. J Combin Theory Ser A 114(6):1118\u20131132. https:\/\/doi.org\/10.1016\/j.jcta.2006.11.006","journal-title":"J Combin Theory Ser A"},{"key":"320_CR34","doi-asserted-by":"crossref","unstructured":"Ouvrard X, Goff JL, Marchand-Maillet S (2017) Adjacency and tensor representation in general hypergraphs part 1: e-adjacency tensor uniformisation using homogeneous polynomials. CoRR arXiv:1712.08189","DOI":"10.1016\/j.endm.2018.11.012"},{"key":"320_CR35","doi-asserted-by":"publisher","unstructured":"Ribeiro BF, Basu P, Towsley D (2012) Multiple random walks to uncover short paths in power law networks. In: 2012 Proceedings IEEE INFOCOM workshops, Orlando, FL, USA, 25\u201330 March 2012, pp 250\u2013255. https:\/\/doi.org\/10.1109\/INFCOMW.2012.6193500","DOI":"10.1109\/INFCOMW.2012.6193500"},{"key":"320_CR36","unstructured":"Schenkel R, Suchanek FM, Kasneci G (2007) YAWN: a semantically annotated wikipedia XML corpus. In: Datenbanksysteme in Business, Technologie und Web (BTW 2007), 12. Fachtagung des GI-Fachbereichs \u201cDatenbanken und Informationssysteme\u201d (DBIS), proceedings, 7.-9. M\u00e4rz 2007, Aachen, Germany, pp 277\u2013291"},{"issue":"1","key":"320_CR37","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/BF01171114","volume":"27","author":"E Sperner","year":"1928","unstructured":"Sperner E (1928) Ein satz \u00fcber untermengen einer endlichen menge. Math Z 27(1):544\u2013548","journal-title":"Math Z"},{"key":"320_CR38","first-page":"179","volume-title":"An experimental study of the small world problem. Social networks","author":"J Travers","year":"1977","unstructured":"Travers J, Milgram S (1977) An experimental study of the small world problem. Social networks. Elsevier, Washington, DC, pp 179\u2013197"},{"key":"320_CR39","first-page":"436","volume":"48","author":"P Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n P (1941) On an extremal problem in graph theory. Matematikai \u00e9s Fizikai Lapok 48:436\u2013452","journal-title":"Matematikai \u00e9s Fizikai Lapok"},{"key":"320_CR40","first-page":"417","volume":"6","author":"P Tur\u00e1n","year":"1961","unstructured":"Tur\u00e1n P (1961) Research problems. Magyar Tud Akad Mat Kutato Internat K\u00f6zl 6:417\u2013423","journal-title":"Magyar Tud Akad Mat Kutato Internat K\u00f6zl"},{"key":"320_CR41","doi-asserted-by":"publisher","unstructured":"Voorhees EM (1986) The efficiency of inverted index and cluster searches. In: SIGIR\u201986, Proceedings of the 9th annual international ACM SIGIR conference on research and development in information retrieval, Pisa, Italy, 8\u201310 Sept 1986, pp 164\u2013174. https:\/\/doi.org\/10.1145\/253168.253203","DOI":"10.1145\/253168.253203"},{"issue":"6684","key":"320_CR42","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts DJ, Strogatz SH (1998) Collective dynamics of \u2018small-world\u2019 networks. Nature 393(6684):440","journal-title":"Nature"},{"key":"320_CR43","doi-asserted-by":"publisher","first-page":"4860531","DOI":"10.1155\/2018\/4860531","volume":"2018","author":"W Yu","year":"2018","unstructured":"Yu W, Sun N (2018) Establishment and analysis of the supernetwork model for Nanjing Metro Transportation System. Complexity 2018:4860531\u20131486053111. https:\/\/doi.org\/10.1155\/2018\/4860531","journal-title":"Complexity"},{"issue":"4","key":"320_CR44","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1145\/296854.277632","volume":"23","author":"J Zobel","year":"1998","unstructured":"Zobel J, Moffat A, Ramamohanarao K (1998) Inverted files versus signature files for text indexing. ACM Trans Database Syst 23(4):453\u2013490. https:\/\/doi.org\/10.1145\/296854.277632","journal-title":"ACM Trans Database Syst"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-020-00320-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-020-00320-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-020-00320-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T22:19:09Z","timestamp":1669328349000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-020-00320-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,27]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["320"],"URL":"https:\/\/doi.org\/10.1007\/s41109-020-00320-z","relation":{},"ISSN":["2364-8228"],"issn-type":[{"type":"electronic","value":"2364-8228"}],"subject":[],"published":{"date-parts":[[2020,10,27]]},"assertion":[{"value":"6 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"79"}}