Editing Hypergraph (section)

==Applications==
Undirected hypergraphs are useful in modelling such things as satisfiability problems,<ref>{{cite conference
 |url          = https://ieeexplore.ieee.org/document/4031385
 |title        = Witnesses for non-satisfiability of dense random 3CNF formulas
 |last1        = Feige
 |first1       = Uriel
 |last2        = Kim
 |first2       = Jeong Han
 |last3        = Ofek
 |first3       = Eran
 |date         = 2006
 |publisher    = IEEE
 |conference   = 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
 |pages        = 497–508
 |doi          = 10.1109/FOCS.2006.78
 |access-date  = 2021-01-20
 |archive-date = 2021-01-27
 |archive-url  = https://web.archive.org/web/20210127222018/https://ieeexplore.ieee.org/document/4031385
 |url-status   = live
}}</ref> databases,<ref name=database /> machine learning,<ref name=hyperx /> and [[Steiner tree problem]]s.<ref>{{cite book
 |last1        = Brazil
 |first1       = M
 |last2        = Zachariasen
 |first2       = M
 |title = Optimal Interconnection Trees in the Plane
 |chapter = Steiner Trees in Graphs and Hypergraphs
 |series = Algorithms and Combinatorics
 |date         = 2015
 |chapter-url          = https://link.springer.com/chapter/10.1007/978-3-319-13915-9_5
 |volume       = 29
 |pages        = 301–317
 |doi          = 10.1007/978-3-319-13915-9_5
 |publisher    = Springer
 |isbn         = 978-3-319-13915-9
 |access-date  = 2021-01-20
 |archive-date = 2021-01-29
 |archive-url  = https://web.archive.org/web/20210129091642/https://link.springer.com/chapter/10.1007/978-3-319-13915-9_5
 |url-status   = live
}}</ref> They have been extensively used in [[machine learning]] tasks as the data model and classifier [[regularization (mathematics)]].<ref>{{citation | last1 = Zhou | first1 = Dengyong | last2 = Huang | first2 = Jiayuan | last3 = Scholkopf | first3 = Bernhard | issue = 2 | title = Advances in Neural Information Processing Systems | pages = 1601–8 | chapter = Learning with hypergraphs: clustering, classification, and embedding | year = 2006 | publisher = MIT Press | isbn = 9780262256919 | chapter-url = https://ieeexplore.ieee.org/document/6287378 | access-date = 2021-07-24 | archive-date = 2021-10-22 | archive-url = https://web.archive.org/web/20211022175429/https://ieeexplore.ieee.org/document/6287378 | url-status = live }}</ref> The applications include [[recommender system]] (communities as hyperedges),<ref>{{citation|last1=Ghoshal | first1=Gourab | last2=Zlatic | first2=Vinko | last3=Caldarelli | first3=Guido | last4=Newman | first4=Mark E.J.| journal = Physical Review E| title = Random Hypergraphs and their applications  |volume=79 |date= 2009 | issue=6 | page=066118 |doi=10.1103/PhysRevE.79.066118 | pmid=19658575 | arxiv=0903.0419 | bibcode=2009PhRvE..79f6118G | s2cid=6391099 }}</ref><ref>{{citation|last1=Tan | first1=Shulong | last2=Bu | first2=Jiajun | last3=Chen | first3=Chun | last4=Xu | first4=Bin | last5=Wang | first5=Can | last6=He | first6=Xiaofei| journal = ACM Transactions on Multimedia Computing, Communications, and Applications| title = Using rich social media information for music recommendation via hypergraph model |url=https://www.researchgate.net/publication/226075153| bibcode=2011smma.book..213T |volume=7S |issue=1 |at=Article 22 |date=October 2011 |doi=10.1145/2037676.2037679 | s2cid=432036 }}</ref> [[image retrieval]] (correlations as hyperedges),<ref>{{citation|last1=Liu | first1=Qingshan | last2=Huang | first2=Yuchi | last3=Metaxas | first3=Dimitris N. |issue = 10–11| journal = Pattern Recognition| title = Hypergraph with sampling for image retrieval| pages=2255–2262| year = 2013| doi=10.1016/j.patcog.2010.07.014 | volume=44}}</ref> and [[bioinformatics]] (biochemical interactions as hyperedges).<ref>{{citation|last1=Patro |first1=Rob | last2=Kingsoford | first2=Carl| issue = 10–11| journal = Bioinformatics| title = Predicting protein interactions via parsimonious network history inference| year = 2013| pages=237–246|doi=10.1093/bioinformatics/btt224 |pmid=23812989 |pmc=3694678 | volume=29}}</ref> Representative hypergraph learning techniques include hypergraph [[spectral clustering]] that extends the [[spectral graph theory]] with hypergraph Laplacian,<ref>{{citation | last1=Gao | first1=Tue | last2=Wang | first2=Meng | last3=Zha | first3=Zheng-Jun | last4=Shen | first4=Jialie | last5=Li | first5=Xuelong | last6=Wu | first6=Xindong | issue=1 | journal=IEEE Transactions on Image Processing | volume=22 | title=Visual-textual joint relevance learning for tag-based social image search | year=2013 | pages=363–376 | url=http://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=2510&context=sis_research | doi=10.1109/tip.2012.2202676 | pmid=22692911 | bibcode=2013ITIP...22..363Y | s2cid=7432373 | access-date=2017-09-22 | archive-date=2017-09-23 | archive-url=https://web.archive.org/web/20170923002956/http://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=2510&context=sis_research | url-status=live }}</ref> and hypergraph [[semi-supervised learning]] that introduces extra hypergraph structural cost to restrict the learning results.<ref>{{citation|last1=Tian|first1=Ze|last2=Hwang|first2=TaeHyun|last3=Kuang|first3=Rui|issue = 21| journal = Bioinformatics| title = A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge| year = 2009| pages=2831–2838|doi=10.1093/bioinformatics/btp467|pmid=19648139| volume=25|doi-access=free}}</ref> For large scale hypergraphs, a distributed framework<ref name=hyperx /> built using [[Apache Spark]] is also available. It can be desirable to study hypergraphs where all hyperedges have the same cardinality; a ''k-uniform hypergraph'' is a hypergraph such that all its hyperedges have size ''k''. (In other words, one such hypergraph is a collection of sets, each such set a hyperedge connecting ''k'' nodes.) So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of unordered triples, and so on.

Directed hypergraphs can be used to model things including telephony applications,<ref>{{cite journal
 |last=Goldstein
 |first=A.
 |date=1982
| title      = A Directed Hypergraph Database: A Model for the Local Loop Telephone Plant
| url        = https://archive.org/details/bstj61-9-2529
| journal    = Bell System Technical Journal
| volume     = 61 |issue=9 |pages=2529–54 |doi=10.1002/j.1538-7305.1982.tb03439.x 
|s2cid=11290643
 }}</ref> detecting [[money laundering]],<ref>{{cite conference
| url = http://fc17.ifca.ai/bitcoin/papers/bitcoin17-final17.pdf
| title = Exchange Pattern Mining in the Bitcoin Transaction Directed Hypergraph
| conference = Financial Cryptography and Data Security
| last1 = Ranshous
| first1 = Stephen
| last2 = Joslyn
| first2 = Cliff
| last3 = Kreyling
| first3 = Sean
| last4 = Nowak
| first4 = Kathleen
| last5 = Samatova
| first5 = Nagiza
| last6 = West
| first6 = Curtis
| last7 = Winters
| first7 = Samuel
| date = 2017
| publisher = Springer
| doi = 10.1007/978-3-319-70278-0_16
| access-date = 2021-01-20
| archive-date = 2021-07-15
| archive-url = https://web.archive.org/web/20210715183918/http://fc17.ifca.ai/bitcoin/papers/bitcoin17-final17.pdf
| url-status = live
}}</ref> operations research,<ref name=ausiello>{{cite journal
 |last1=Ausiello
 |first1=Giorgio
 |last2=Laura
 |first2=Luigi
 |date=2017
| title      = Directed hypergraphs: Introduction and fundamental algorithms - A survey
| pages = 293–306
| doi = 10.1016/j.tcs.2016.03.016
| journal    = Theoretical Computer Science
| volume     = 658
| doi-access= free
}}</ref> and transportation planning. They can also be used to model [[Horn-satisfiability]].<ref name=gallo />