Abstract-interaktioner i många verkliga fenomen kan förklaras med en stark hierarkisk struktur. Vanligtvis är denna struktur eller rankning inte känd; istället har vi bara observerat resultat av interaktioner, och målet är att härleda hierarkin från dessa observationer. Upptäcka en hierarki i samband med riktade nätverk kan formuleras på följande sätt: med tanke på en graf, partition hörn i nivåer så att, helst, det bara finns kanter från övre nivåer till lägre nivåer. Det idealiska fallet kan bara hända om grafen är acyklisk. Följaktligen måste vi i praktiken införa en strafffunktion som straffar kanter som bryter mot hierarkin. En praktisk variant av ett sådant straff är vånda, där varje brottsbenägenhet bestraffas på grundval av överträdelsens allvar. Hierarki minimerar vånda kan upptäckas i O(m 2 ) tid, och mycket snabbare i praktiken. I det här dokumentet introducerar vi flera tillägg till vånda. Vi utökar definitionen av viktade grafer och tillåter en kardinalitetsbegränsning som begränsar antalet nivåer. Även om dessa är konceptuellt triviala förlängningar, nuvarande algoritmer kan inte hantera dem, inte heller kan de enkelt förlängas. Vi tillhandahåller en exakt algoritm av O(m 2 log n) tid genom att visa kopplingen av smärta till kapaciated cirkulation problem. Vi visar också att denna gräns i själva verket är pessimistisk och att vi kan beräkna vånda för stora datamängder. Dessutom visar vi att vi kan beräkna vånda i polynom tid för alla konvexa straff, och, för att slutföra bilden, visar vi att minimering hierarki med någon konkava straff är ett NP-hårda problem.
Dessutom visade Tatti REF att minimerande vånda är NP-hård för eventuella konkava straff medan polynom förblir polynom för någon konvex strafffunktion.
Hierarchies in Directed Networks
{'venue': '2015 IEEE International Conference on Data Mining', 'journal': '2015 IEEE International Conference on Data Mining', 'mag_field_of_study': ['Computer Science']}