[FRIAM] hypergraphs

Sun Feb 27 09:57:51 EST 2022

Eric --

Thank you for the thank you.

The research certainly seems to be all over the place.  The article sounded
like the voice of an NSF program officer seeking more proposals to fund,
too.

This reminded me of my first published paper (Roger E Critchlow Jr and
Steven Stearns, *The Structure of Food Webs*, *The American Naturalist* 1982,
Vol. 120, pp. 478-499, which was a response to Joel Cohen's *Food Webs and
Niche Space*. *Monographs in Population Biology* 11. 1978. Princeton, NJ:
Princeton University Press. 190 pp.  Cohen adapted an algorithm for
analysing the overlaps of archaeological finds in sedimentary deposits to
asking if food web relations had the structure of overlapping intervals.  A
very clever idea, but Cohen didn't program the algorithm, he had someone
write an APL program that he used to analyse a collection of food webs.
And he found that lots of food webs had the structure of overlapping
intervals, which he identified as one-dimensional niche descriptors

Working from the original source for the algorithm, D.R. Fulkerson, O.A.
Gross, *Incidence matrices and interval graphs*, *Pacific J. Math.* I5 (3)
(1965) 835-855, I recoded the algorithm from scratch and obtained results
that agreed with Cohen's for most of the data set, but disagreed on a few
instances.  It turned out that I had simplified the algorithm by omitting
the step which reduced the food web incidence matrix to its maximal clique
matrix, but I had correctly coded the algorithm for testing an incidence
matrix for consecutive ones (CIP).  An incidence matrix has a 1 if the row
eats the column and 0 otherwise.  An incidence matrix has CIP if you can
permute the columns so each row has all its ones in consecutive columns.  A
food web with CIP always produces a maximal clique with CIP, hence the
agreement in results, but maximal cliques with CIP can arise from food webs
without CIP, hence the disagreements in results.

Many of Cohen's food webs can permute to consecutive ones in both rows and
columns, which gives you a block structured matrix where the ones are all
neatly organized.  The block structure comes from the maximal cliques, the
transitive closure of predator A and B have a common prey, or the
transitive closure of prey C and D have a common predator. Consecutive ones
in a component might be evidence that the relation grew by diversification
from a founder seed.

I hadn't thought about this for a long while.  Tracking down the Fulkerson
& Gross citation via google I found João Meidanis, OscarPorto, Guilherme
P.Telles, *On the consecutive ones property*, *Discrete Applied
Mathematics *Volume 88, Issues 1–3, 9 November 1998, Pages 325-354, and
discovered the applications of consecutive ones to sequencing contig
assembly and chip circuit floor planning.

-- rec --

On Thu, Feb 24, 2022 at 12:02 PM David Eric Smith <desmith at santafe.edu>
wrote:

> Thank you for this, Roger,
>
> Very good to have.
>
> Eric
>
>
>
> On Feb 24, 2022, at 11:26 AM, Roger Critchlow <rec at elf.org> wrote:
>
> There's a little news burp about hypergraphs in this month's CACM, mostly
> about how hard they are, except when they reduce to graphs, and that the
> NSF is funding some research efforts.
>
> CACM, MARCH 2022, VOL . 65, NO. 3, DOI:10.1145/3510550
> Chris Edwards, A Group Effort, Researchers look for new insights in the
> world of hypergraphs
>
> Further Reading
> Agarwal, S., Branson, K., and Belongie, S. Higher-Order Learning with
> Graphs, Proceedings of the 23rd International Conference on Machine
> Learning (ICML 2006), pages 17–24
>
> Jost, J. and Mulas, R., Normalized Laplace Operators for Hypergraphs with
> Real Coefficients, Journal of Complex Networks, Volume 9, Issue 1, February
> 2021, cnab009
>
> Hillar, C.J., and Lim, L.-H., Most Tensor Problems are NP-Hard, Journal of
> the ACM, 60, 6, Article 45, November 2013
>
> Veldt, N., Benson, A.R., and Kleinberg, J. Higher-order Homophily is
> Combinatorially Impossible, arXiv: 2103.11818 (2021), https://arxiv.org/
> abs/2103.1181
>
> -- rec --
> Further ReadingAgarwal, S., Branson, K., and Belongie, S.Higher-Order
> Learning with GraphsProceedings of the 23rd International Conference on
> Machine Learning (ICML 2006), pages 17–24Jost, J. and Mulas, R.Normalized
> Laplace Operators for Hypergraphs with Real CoefficientsJournal of
> Complex Networks, Volume 9, Issue 1, February 2021, cnab009Hillar, C.J.,
> and Lim, L.-H.Most Tensor Problems are NP-HardJournal of the ACM, 60, 6,
> Article 45, November 2013Veldt, N., Benson, A.R., and Kleinberg, J.Higher-order
> Homophilyis Combinatorially ImpossiblearXiv: 2103.11818 (2021),
> https://arxiv.org/abs/2103.11818
>
> .-- .- -. - / .- -.-. - .. --- -. ..--.. / -.-. --- -. .--- ..- --. .- - .
> FRIAM Applied Complexity Group listserv
> Zoom Fridays 9:30a-12p Mtn UTC-6
> https://linkprotect.cudasvc.com/url?a=https%3a%2f%2f%2f%2fbit.ly%2fvirtualfriam&c=E,1,wESXHLhF_A9fMgD1_PYGHFY4lKSdDoNrN_I23_B5OgTdlhrFbN1sYHxd1P4_5Gd1TPkdpHocQ30zMHI_S3D0j3Kh6MFNq8vCpEVdxn3mtIrhRQU2&typo=1
> un/subscribe
> https://linkprotect.cudasvc.com/url?a=http%3a%2f%2fredfish.com%2fmailman%2flistinfo%2ffriam_redfish.com&c=E,1,gbR3NW7yvh6njQjIm3mwfCyWde1zchF6xw-hiORaZXDPAOOPSB2Lue-k0ml57EHVTf43W2y6b1JTdC9u0DCD8Lb_vXSr3FAlD_SWeS0ZEg,,&typo=1
> FRIAM-COMIC
> https://linkprotect.cudasvc.com/url?a=http%3a%2f%2ffriam-comic.blogspot.com%2f&c=E,1,jnDXzQpquRiGHWw_bpK81A-V0LrQtWWVZXyNsb0bDiK60I1ZdCSP4XyI6mKCm5Jm7bZrNcM5mO16cJgdz8Tpc8Jp6lNscF-XMmtKrUuhaUsx4Cv-4IMDsXE,&typo=1
> archives:
> 5/2017 thru present
> https://linkprotect.cudasvc.com/url?a=https%3a%2f%2fredfish.com%2fpipermail%2ffriam_redfish.com%2f&c=E,1,XzgeCCgWXbci1RFJi0qrfDM_Vl_ixyh1EDxsZnBoDE4a2xT07FVU6b8B8abjydqCEKgL1SOU2Ywz5JQVkLDO3FgrNyTzQZlHELrUnH0Kd1NnSwF7dKEtuJKQ24k,&typo=1
> 1/2003 thru 6/2021  http://friam.383.s1.nabble.com/
>
>
>
> .-- .- -. - / .- -.-. - .. --- -. ..--.. / -.-. --- -. .--- ..- --. .- - .
> FRIAM Applied Complexity Group listserv
> Zoom Fridays 9:30a-12p Mtn UTC-6  bit.ly/virtualfriam
> un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
> FRIAM-COMIC http://friam-comic.blogspot.com/
> archives:
>  5/2017 thru present https://redfish.com/pipermail/friam_redfish.com/
>  1/2003 thru 6/2021  http://friam.383.s1.nabble.com/
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://redfish.com/pipermail/friam_redfish.com/attachments/20220227/a707b99e/attachment-0001.html>