{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:28:13Z","timestamp":1740122893954,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"15","license":[{"start":{"date-parts":[[2020,7,18]],"date-time":"2020-07-18T00:00:00Z","timestamp":1595030400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,18]],"date-time":"2020-07-18T00:00:00Z","timestamp":1595030400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Multimed Tools Appl"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Highlighting important information of a network is commonly achieved by using random walks related to diffusion over such structures. Complex networks, where entities can have multiple relationships, call for a modeling based on hypergraphs. But, the limitation of hypergraphs to binary entities in co-occurrences has led us to introduce a new mathematical structure called hyperbaggraphs, that relies on multisets. This is not only a shift in the designation but a real change of mathematical structure, with a new underlying algebra. Diffusion processes commonly start with a stroke at one vertex and diffuse over the network. In the original conference article\u2014(Ouvrard et al. 2018)\u2014that this article extends we have proposed a two-phase step exchange-based diffusion scheme, in the continuum of spectral network analysis approaches, that takes into account the multiplicities of entities. This diffusion scheme allows to highlight information not only at the level of the vertices but also at the regrouping level. In this paper, we present new contributions: the proofs of conservation and convergence of the extracted sequences of the diffusion process, as well as the illustration of the speed of convergence and comparison between classical and modified random walks; the algorithms of the exchange-based diffusion and the modified random walk; the application to two use cases, one based on Arxiv publications and another based on Coco dataset images. All the figures have been revisited in this extended version to take the new developments into account.<\/jats:p>","DOI":"10.1007\/s11042-020-09176-y","type":"journal-article","created":{"date-parts":[[2020,7,18]],"date-time":"2020-07-18T12:02:32Z","timestamp":1595073752000},"page":"22429-22464","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Exchange-based diffusion in Hb-Graphs"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4054-2771","authenticated-orcid":false,"given":"Xavier","family":"Ouvrard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Marie","family":"Le Goff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane","family":"Marchand-Maillet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,18]]},"reference":[{"key":"9176_CR1","unstructured":"Bellaachia A, Al-Dhelaan M (2013) Random walks in hypergraph. In: Proceedings of the 2013 international conference on applied mathematics and computational methods, Venice, Italy, pp 187\u2013194"},{"key":"9176_CR2","doi-asserted-by":"crossref","unstructured":"Bendersky M, Croft WB (2012) Modeling higher-order term dependencies in information retrieval using query hypergraphs, vol 941, ACM Press","DOI":"10.1145\/2348283.2348408"},{"key":"9176_CR3","volume-title":"Graphs and hypergraphs, vol 7","author":"C Berge","year":"1973","unstructured":"Berge C (1973) Graphs and hypergraphs, vol 7. North Holland, Amsterdam"},{"key":"9176_CR4","volume-title":"Mathematical engineering","author":"A Bretto","year":"2013","unstructured":"Bretto A, Theory Hypergraph (2013) Mathematical engineering. Springer International Publishing, Heidelberg"},{"key":"9176_CR5","doi-asserted-by":"crossref","unstructured":"Bu J, Tan S, Chen C, Wang C, Wu H, Zhang L, He X (2010) Music recommendation by unified hypergraph: combining social media information and music content. In: Proceedings of the international conference on Multimedia - MM \u201910, (Firenze, Italy), vol 391. ACM Press","DOI":"10.1145\/1873951.1874005"},{"key":"9176_CR6","doi-asserted-by":"crossref","unstructured":"Chauve C, Patterson M, Rajaraman A (2013) Hypergraph covering problems motivated by genome assembly questions. In: Combinatorial algorithms, vol 8288. Springer, Berlin, pp 428\u2013432","DOI":"10.1007\/978-3-642-45278-9_37"},{"key":"9176_CR7","unstructured":"Csurka G, Dance C, Fan L, Willamowski J, Bray C (2004) Visual categorization with bags of keypoints. In: Workshop on statistical learning in computer vision, ECCV. Prague, vol 1, pp 1\u20132"},{"key":"9176_CR8","doi-asserted-by":"crossref","unstructured":"Cummins N, Amiriparian S, Ottl S, Gerczuk M, Schmitt M, Schuller B (2018) Multimodal bag-of-Words for Cross Domains Sentiment Analysis. In: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), (Calgary, AB). IEEE, p 2018","DOI":"10.1109\/ICASSP.2018.8462660"},{"key":"9176_CR9","doi-asserted-by":"crossref","unstructured":"Deselaers T, Pimenidis L, Ney H (2008) Bag-of-visual-words models for adult image classification and filtering. In: 2008 19th international conference on pattern recognition, (Tampa, FL, USA). IEEE, pp 1\u20134","DOI":"10.1109\/ICPR.2008.4761366"},{"key":"9176_CR10","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.cviu.2013.10.012","volume":"120","author":"A Ducournau","year":"2014","unstructured":"Ducournau A, Bretto A (2014) Random walks in directed hypergraphs and application to semi-supervised image segmentation. Comput Vis Image Underst 120:91\u2013102","journal-title":"Comput Vis Image Underst"},{"key":"9176_CR11","doi-asserted-by":"publisher","first-page":"4290","DOI":"10.1109\/TIP.2012.2199502","volume":"21","author":"Y Gao","year":"2012","unstructured":"Gao Y, Wang M, Tao D, Ji R, Dai Q (2012) 3-D Object retrieval and recognition with hypergraph analysis. IEEE Trans Image Process 21:4290\u20134303","journal-title":"IEEE Trans Image Process"},{"issue":"1","key":"9176_CR12","first-page":"37","volume":"2","author":"K Girish","year":"2012","unstructured":"Girish K, Jacob JS (2012) On multiset topologies. Theory Appl Math Comput Sci 2(1):37\u201352","journal-title":"Theory Appl Math Comput Sci"},{"key":"9176_CR13","unstructured":"Grossman JW, Ion PD (1995) On a portion of the well-known collaboration graph. In: Congressus Numerantium, pp 129\u2013132"},{"key":"9176_CR14","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1080\/00437956.1954.11659520","volume":"10","author":"ZS Harris","year":"1954","unstructured":"Harris ZS (1954) Distributional structure. WORD 10:146\u2013162","journal-title":"WORD"},{"key":"9176_CR15","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1109\/92.748202","volume":"7","author":"G Karypis","year":"1999","unstructured":"Karypis G, Aggarwal R, Kumar V, Shekhar S (1999) Multilevel hypergraph partitioning: applications in VLSI domain. IEEE Trans Very Large Scale Integr VLSI Syst 7:69\u201379","journal-title":"IEEE Trans Very Large Scale Integr VLSI Syst"},{"key":"9176_CR16","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/j.neucom.2017.05.046","volume":"266","author":"H Kim","year":"2017","unstructured":"Kim H, Kim H, Cho S (2017) Bag-of-concepts: Comprehending document representation through clustering words in distributed representation. Neurocomputing 266:336\u2013352","journal-title":"Neurocomputing"},{"key":"9176_CR17","doi-asserted-by":"crossref","unstructured":"Lee J, Cho M, Lee KM (2011) Hyper-graph matching via reweighted random walks. In: Computer Vision and Pattern Recognition (CVPR) IEEE Conference on, p 2011","DOI":"10.1109\/CVPR.2011.5995387"},{"key":"9176_CR18","doi-asserted-by":"crossref","unstructured":"Lin T-Y, Maire M, Belongie S, Hays J, Perona P, Ramanan D, Doll\u00e1r P, Zitnick CL (2014) Microsoft coco: Common objects in context. In: European conference on computer vision. tex.organization: Springer, pp 740\u2013755","DOI":"10.1007\/978-3-319-10602-1_48"},{"key":"9176_CR19","doi-asserted-by":"crossref","unstructured":"Lu L, Peng X (2011) High-ordered random walks and generalized laplacians on hypergraphs, Springer","DOI":"10.1007\/978-3-642-21286-4_2"},{"key":"9176_CR20","doi-asserted-by":"crossref","unstructured":"Ma S, Sun X, Wang Y, Lin J (2018) Bag-of-words as target for neural machine translation, arXiv:1805.04871","DOI":"10.18653\/v1\/P18-2053"},{"key":"9176_CR21","doi-asserted-by":"crossref","unstructured":"Minaee S, Wang S, Wang Y, Chung S, Wang X, Fieremans E, Flanagan S, Rath J, Lui YW (2017) 2017 Identifying mild traumatic brain injury patients from MR images using bag of visual words. In: IEEE Signal Processing in Medicine and Biology Symposium (SPMB), (Philadelphia, PA). IEEE, pp 1\u20135","DOI":"10.1109\/SPMB.2017.8257054"},{"key":"9176_CR22","doi-asserted-by":"publisher","first-page":"016131","DOI":"10.1103\/PhysRevE.64.016131","volume":"64","author":"MEJ Newman","year":"2001","unstructured":"Newman MEJ (2001) Scientific collaboration networks. I. Network construction and fundamental results. Phys Rev E 64:016131","journal-title":"Phys Rev E"},{"key":"9176_CR23","doi-asserted-by":"publisher","first-page":"016132","DOI":"10.1103\/PhysRevE.64.016132","volume":"64","author":"MEJ Newman","year":"2001","unstructured":"Newman MEJ (2001) Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. Phys Rev E 64:016132","journal-title":"Phys Rev E"},{"key":"9176_CR24","doi-asserted-by":"crossref","unstructured":"Ouvrard X, Le Goff J-M, Marchand-Maillet S (2018) Diffusion by exchanges in hb-graphs : highlighting complex relationships. In: CBMI proceedings","DOI":"10.1109\/CBMI.2018.8516525"},{"key":"9176_CR25","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.endm.2018.11.011","volume":"70","author":"X Ouvrard","year":"2018","unstructured":"Ouvrard X, Le Goff J-M, Marchand-Maillet S (2018) Hypergraph modeling and visualisation of complex co-occurence networks. Electron Notes Discrete Math 70:65\u201370","journal-title":"Electron Notes Discrete Math"},{"key":"9176_CR26","unstructured":"Ouvrard X, Le Goff J-M, Marchand-Maillet S (2018) Adjacency and tensor representation in general hypergraphs. Part 2: multisets. Hb-graphs and Related e-adjacency Tensors. arXiv:1805.11952"},{"key":"9176_CR27","unstructured":"Ouvrard X, Le Goff J-M, Marchand-Maillet S (2019) On Hb-graphs and their Application to General Hypergraph e-adjacency Tensor. In: MCCCC 32 special volume of the journal of combinatorial mathematics and combinatorial computing to be published"},{"key":"9176_CR28","doi-asserted-by":"crossref","unstructured":"Ouvrard X, Le Goff J-M, Marchand-Maillet S (2019) Diffusion by exchanges in hb-graphs: highlighting complex relationships extended version.arXiv:1809.00190v2","DOI":"10.1109\/CBMI.2018.8516525"},{"key":"9176_CR29","doi-asserted-by":"crossref","unstructured":"Ouvrard X, Le Goff J-M, Marchand-Maillet S (2020) The hyperbaggraph dataedron: an enriched browsing experience of datasets. In: LNCS, 46th international conference on current trends in theory and practice of computer science (SOFSEM 2020)","DOI":"10.1007\/978-3-030-38919-2_30"},{"key":"9176_CR30","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.cviu.2016.03.013","volume":"150","author":"X Peng","year":"2016","unstructured":"Peng X, Wang L, Wang X, Qiao Y (2016) Bag of visual words and fusion methods for action recognition:, Comprehensive study and good practice. Comput Vis Image Und 150:109\u2013125","journal-title":"Comput Vis Image Und"},{"key":"9176_CR31","doi-asserted-by":"publisher","first-page":"1193","DOI":"10.1111\/1911-3846.12089","volume":"32","author":"L Purda","year":"2015","unstructured":"Purda L, Skillicorn D (2015) Accounting variables, deception, and a bag of words: assessing the tools of fraud detection. Contemp Account Res 32:1193\u20131223","journal-title":"Contemp Account Res"},{"key":"9176_CR32","unstructured":"Schmitt M, Janott C, Pandit V, Qian K, Heiser C, Hemmert W, Schuller B (2016) A bag-of-audio-words approach for snore sounds\u2019 excitation localisation. VDE"},{"key":"9176_CR33","doi-asserted-by":"crossref","unstructured":"Shekhar R, Jawahar C (2012) Word image retrieval using bag of visual words. In: 2012 10th IAPR international workshop on document analysis systems, (Gold Coast, Queenslands, TBD, Australia). IEEE, pp 297\u2013301","DOI":"10.1109\/DAS.2012.96"},{"key":"9176_CR34","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1016\/j.patcog.2017.09.018","volume":"74","author":"FB Silva","year":"2018","unstructured":"Silva FB, Werneck RDO, Goldenstein S, Tabbone S, Torres RDS (2018) Graph-based bag-of-words for classification. Pattern Recogn 74:266\u2013285","journal-title":"Pattern Recogn"},{"issue":"3","key":"9176_CR35","first-page":"73","volume":"37","author":"D Singh","year":"2007","unstructured":"Singh D, Ibrahim A, Yohanna T, Singh J (2007) An overview of the applications of multisets. Novi Sad J Math 37(3):73\u201392","journal-title":"Novi Sad J Math"},{"key":"9176_CR36","doi-asserted-by":"crossref","unstructured":"Sivic J, Zisserman A (2003) Video google: a text retrieval approach to object matching in videos. In: Proceedings 9th IEEE international conference on computer vision, (Nice, France). IEEE, vol 2, pp 1470\u20131477","DOI":"10.1109\/ICCV.2003.1238663"},{"key":"9176_CR37","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1007\/s11192-010-0226-4","volume":"85","author":"C Taramasco","year":"2010","unstructured":"Taramasco C, Cointet J-P, Roth C (2010) Academic team formation as evolving hypergraphs. Scientometrics 85:721\u2013740","journal-title":"Scientometrics"},{"key":"9176_CR38","volume-title":"Chemical reaction networks: a graph-theoretical approach","author":"ON Temkin","year":"1996","unstructured":"Temkin ON, Zeigarnik AV, Bonchev D (1996) Chemical reaction networks: a graph-theoretical approach. CRC Press, Boca Raton"},{"key":"9176_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.5402\/2012\/376804","volume":"2012","author":"C-F Tsai","year":"2012","unstructured":"Tsai C-F (2012) Bag-of-words representation in image annotation: a review. ISRN Artif Intell 2012:1\u201319","journal-title":"ISRN Artif Intell"},{"key":"9176_CR40","doi-asserted-by":"publisher","first-page":"4437","DOI":"10.1109\/TIP.2018.2837219","volume":"27","author":"Y Wang","year":"2018","unstructured":"Wang Y, Zhu L, Qian X, Han J (2018) Joint hypergraph learning for tag-Based image retrieval. IEEE Trans Image Process 27:4437\u20134451","journal-title":"IEEE Trans Image Process"},{"key":"9176_CR41","doi-asserted-by":"crossref","unstructured":"Xu Z, Du J, Ye L, Fan D (2016) Multi-feature indexing for image retrieval based on hypergraph. In: 2016 4th International Conference on Cloud Computing and Intelligence Systems (CCIS), (Beijing, China). IEEE, pp 494\u2013500","DOI":"10.1109\/CCIS.2016.7790309"},{"key":"9176_CR42","doi-asserted-by":"publisher","first-page":"2080","DOI":"10.1109\/TVCG.2013.167","volume":"19","author":"J Zhao","year":"2013","unstructured":"Zhao J, Collins C, Chevalier F, Balakrishnan R (2013) Interactive exploration of implicit and explicit relations in faceted datasets. IEEE Trans Vis Comput Graph 19:2080\u20132089","journal-title":"IEEE Trans Vis Comput Graph"},{"key":"9176_CR43","doi-asserted-by":"publisher","first-page":"2756","DOI":"10.1109\/TCYB.2014.2383389","volume":"45","author":"L Zhu","year":"2015","unstructured":"Zhu L, Shen J, Jin H, Zheng R, Xie L (2015) Content-based visual landmark search via multimodal hypergraph learning. IEEE Trans Cybern 45:2756\u20132769","journal-title":"IEEE Trans Cybern"},{"key":"9176_CR44","doi-asserted-by":"crossref","unstructured":"Zhou D, Huang J, Sch\u00f6lkopf B (2007) Learning with hypergraphs: Clustering, classification, and embedding. In: Advances in neural information processing systems, pp 1601\u20131608","DOI":"10.7551\/mitpress\/7503.003.0205"}],"container-title":["Multimedia Tools and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11042-020-09176-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11042-020-09176-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11042-020-09176-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T12:10:26Z","timestamp":1696421426000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11042-020-09176-y"}},"subtitle":["Highlighting complex relationships in multimedia collections (extended version)"],"short-title":[],"issued":{"date-parts":[[2020,7,18]]},"references-count":44,"journal-issue":{"issue":"15","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["9176"],"URL":"https:\/\/doi.org\/10.1007\/s11042-020-09176-y","relation":{},"ISSN":["1380-7501","1573-7721"],"issn-type":[{"type":"print","value":"1380-7501"},{"type":"electronic","value":"1573-7721"}],"subject":[],"published":{"date-parts":[[2020,7,18]]},"assertion":[{"value":"15 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 May 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 July 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}