Browsing by Author "Ordozgoiti Rubio, Bruno"

Filter results by typing the first few letters
Now showing 1 - 2 of 2
  • Discovering conflicting groups in signed networks
    (2020) Tzeng, Ruo-Chun; Ordozgoiti Rubio, Bruno; Gionis, Aristides
     A4 Artikkeli konferenssijulkaisussa
    Signed networks are graphs where edges are annotated with a positive or negative sign, indicating whether an edge interaction is friendly or antagonistic. Signed networks can be used to study a variety of social phenomena, such as mining polarized discussions in social media, or modeling relations of trust and distrust in online review platforms. In this paper we study the problem of detecting k conflicting groups in a signed network. Our premise is that each group is positively connected internally and negatively connected with the other k−1 groups. An important aspect of our formulation is that we are not searching for a complete partition of the signed network, instead, we allow other nodes to be neutral with respect to the conflict structure we are searching. As a result, the problem we tackle differs from previously studied problems, such as correlation clustering and k-way partitioning. To solve the conflicting-group discovery problem, we derive a novel formulation in which each conflicting group is naturally characterized by the solution to the maximum discrete Rayleigh's quotient (\maxdrq) problem. We present two spectral methods for finding approximate solutions to the \maxdrq problem, which we analyze theoretically. Our experimental evaluation shows that, compared to state-of-the-art baselines, our methods find solutions of higher quality, are faster, and recover ground truth conflicting groups with higher accuracy.
  • Recent results and open problems in spectral algorithms for signed graphs
    (2021-08-28) Ordozgoiti Rubio, Bruno
     A4 Artikkeli konferenssijulkaisussa
    In signed graphs, edges are labeled with either a positive or a negative sign.This small modification greatly enriches the representation capabilities of graphs.However, their spectral properties undergo significant changes, introducing newchallenges in related optimization problems. In this extended abstract we discussrecent results in spectral methods for signed graph partitioning and communitydetection, and propose open problems arising in this context.