SIGNED GRAPH DOMINATION FOR RECOMMENDATION SYSTEMS: A NOVEL APPROACH USING COSINE SIMILARITY AND OPPOSITE PREFERENCE MATRICES

Abstract

This dissertation studies recommendation systems from the viewpoint of signed graph domination. Standard item–item recommenders usually build an un signed similarity graph: two movies are connected when their rating vectors look simi lar, while missing or disliked interactions are treated mainly as absence of information. In many catalogues this is too weak a representation. Low ratings also carry structure, because they indicate preference opposition rather than mere non-observation. The work therefore constructs a signed item–item graph in which positive edges represent rating-vector similarity and negative edges represent opposite preference behaviour. The proposed construction has two parts. Positive similarity is measured by the cosine similarity between item rating vectors, as in memory-based collabora tive filtering (21). Negative similarity is obtained from an opposite preference matrix formed from high-rating and low-rating indicator matrices. A dual-threshold domina tion rule is then introduced: item i1 dominates item i2 when the positive similarity is at least α and the negative similarity is at most β. A greedy dominating-set algorithm is applied to this signed relation to extract a compact subset of representative items. The framework is motivated by signed graph domination and signed-fuzzy domination (1; 20; 29), but is adapted to real-valued similarity matrices arising from recommenda tion data. The method is evaluated on the MovieLens ml-latest-small dataset (11), containing 100,836 ratings by 610 users on 9,724 movies. For the top 100 most rated movies, the choice α = β = 0.5 produces a dominating set of 9 movies with full structural coverage of the selected catalogue. The set covers 12 distinct genres, com pared with 10 genres for a popularity baseline of the same size, and only two movies are common to both sets. These results indicate that structural signed domination se lects representatives differently from raw popularity. The dissertation also connects the empirical construction to balance theory, Acharya’s algebraic signed domination, Joseph and Joseph’s signed Roman domina tion, and the domination-integrity framework of Sankar et al. (1; 20; 29). The main conclusion is that signed edge information can be used not only for prediction or em bedding, but also for selecting small, interpretable and structurally covering item sets.