• search hit 2 of 5
Back to Result List

A relevance feedback approach for social network clustering in the context of triangle inequality violations

Ein Relevanz-Feedback-Ansatz für das Clustering sozialer Netzwerke im Kontext von Dreiecks-Ungleichheitsverstößen

  • People in a social network are connected, and their homogeneity is reflected by the similarity of their attributes. For effective clustering, the similarities among people within a cluster must be much higher than the similarities between different clusters. Traditional clustering algorithms like hierarchical (agglomerative) or k-medoids take distances between objects as input and find clusters of objects. The distance functions used should comply with the triangle inequality (TI) property, but sometimes this property may be violated, thus negatively impacting the quality of the generated clusters. However, in social networks, meaningful clusters can be found even though TI violates. One possibility is a quantum-logic-based clique-guided non-TI clustering approach. The commuting quantum query language (CQQL) is the base for this approach. The CQQL allows the formulation of queries that incorporate both Boolean and similarity conditions. It calculates the similarity value between two objects. Furthermore, attributes may not havePeople in a social network are connected, and their homogeneity is reflected by the similarity of their attributes. For effective clustering, the similarities among people within a cluster must be much higher than the similarities between different clusters. Traditional clustering algorithms like hierarchical (agglomerative) or k-medoids take distances between objects as input and find clusters of objects. The distance functions used should comply with the triangle inequality (TI) property, but sometimes this property may be violated, thus negatively impacting the quality of the generated clusters. However, in social networks, meaningful clusters can be found even though TI violates. One possibility is a quantum-logic-based clique-guided non-TI clustering approach. The commuting quantum query language (CQQL) is the base for this approach. The CQQL allows the formulation of queries that incorporate both Boolean and similarity conditions. It calculates the similarity value between two objects. Furthermore, attributes may not have equal impact on similarity and affect the resulting clusters. CQQL incorporates weights to express the varying importance of sub-conditions in a query while preserving consistency with Boolean algebra. This enables personalization of results through relevance feedback (RF). The main challenge of comparing clusterings is that there is no ground truth data. In such situations, human-generated gold standard clustering can be used. The question is how to compare the performance of clusterings. A noteworthy technique involves counting the pairs of objects that are grouped identically in both clusterings. By doing so, a clustering distance is calculated that measures the dissimilarity. To validate the non-TI clustering approach, experiments are conducted on social networks of different sizes. Three central questions are addressed by the experiments mentioned: first, is it possible to find meaningful clusters even though TI violates; second, how does a user interact with the system to provide feedback based on their needs; and third, how fast do the detected clusters based on the proposed approach converge to the ideal solution? To sum up, the experiments’ objective is to demonstrate the validity of a theoretical approach. The research findings presented here provide sufficient evidence for detecting meaningful clusters based on user interaction. Furthermore, the experiments clearly demonstrate that the non-TI clustering approach can be used as an RF technique in clustering.show moreshow less
  • Menschen in einem sozialen Netzwerk sind miteinander verbunden. Ihre Homogenität spiegelt sich in der Ähnlichkeit ihrer Eigenschaften wider. Für ein effektives Clusterbildung müssen die Ähnlichkeiten zwischen Personen innerhalb eines Clusters größer sein als die Ähnlichkeiten zwischen Personen verschiedener Cluster. Herkömmliche Clustering Algorithmen wie etwa hierarchisches (agglomeratives) oder k-Medoids nutzen Abstände zwischen Objekten zum Finden von Clustern von Objekten. Die verwendete Abstandsfunktion sollte die Eigenschaft der Dreiecksungleichheit (TI) aufweisen, aber manchmal kann diese Eigenschaft verletzt sein, was sich negativ auf die Qualität der erzeugten Cluster auswirken kann. In sozialen Netzwerken können jedoch sinnvolle Cluster gefunden werden, auch wenn die TI verletzt wird. Eine Möglichkeit ist ein auf Quantenlogik basierende cliquengesteuerten Non-TI-Clustering-Ansatz. Die Commuting Quantum Query Language (CQQL) ist die Grundlage für diesen Ansatz. Die CQQL erlaubt die Formulierung von Abfragen, die sowohlMenschen in einem sozialen Netzwerk sind miteinander verbunden. Ihre Homogenität spiegelt sich in der Ähnlichkeit ihrer Eigenschaften wider. Für ein effektives Clusterbildung müssen die Ähnlichkeiten zwischen Personen innerhalb eines Clusters größer sein als die Ähnlichkeiten zwischen Personen verschiedener Cluster. Herkömmliche Clustering Algorithmen wie etwa hierarchisches (agglomeratives) oder k-Medoids nutzen Abstände zwischen Objekten zum Finden von Clustern von Objekten. Die verwendete Abstandsfunktion sollte die Eigenschaft der Dreiecksungleichheit (TI) aufweisen, aber manchmal kann diese Eigenschaft verletzt sein, was sich negativ auf die Qualität der erzeugten Cluster auswirken kann. In sozialen Netzwerken können jedoch sinnvolle Cluster gefunden werden, auch wenn die TI verletzt wird. Eine Möglichkeit ist ein auf Quantenlogik basierende cliquengesteuerten Non-TI-Clustering-Ansatz. Die Commuting Quantum Query Language (CQQL) ist die Grundlage für diesen Ansatz. Die CQQL erlaubt die Formulierung von Abfragen, die sowohl Boole’sche als auch Ähnlichkeitsbedingungen enthalten. Sie berechnet den Ähnlichkeitswert zwischen zwei Objekten. Darüber hinaus haben die Attribute möglicherweise nicht den gleichen Einfluss auf die Ähnlichkeit und beeinflussen die resultierenden Cluster. CQQL bietet ein Gewichtungsschema, um die unterschiedliche Wichtigkeit von Unterbedingungen in einer Abfrage auszudrücken, wobei jedoch die Konsistenz mit der Boole’schen Algebra gewahrt bleibt. Dies ermöglicht eine Personalisierung der Ergebnisse durch Relevanz-Feedback (RF). Die größte Herausforderung beim Vergleich von Clustern besteht darin, dass es keine Ground-Truth-Daten gibt. In solchen Situationen kann ein von Menschen erstelltes Goldstandard-Clustering verwendet werden. Die Frage ist, wie die Leistung von Clustern vergleichen kann. Eine bemerkenswerte Technik besteht darin, die Paare von Objekten zu zählen, die in beiden Clustern gleich gruppiert sind. Auf diese Weise wird ein Clustering-Abstand berechnet, der die Unähnlichkeit misst. Um den Non-TI-Clustering-Ansatzes zu überprüfen, werden Experimente mit sozialen Netzwerken unterschiedlicher Größe durchgeführt. Drei zentrale Fragen werden in den Experimenten behandelt: Erstens, ist es möglich, sinnvolle Cluster zu finden, auch wenn die TI verletzt wird; zweitens, wie interagiert ein Benutzer mit dem System, um Feedback auf der Grundlage seiner Bedürfnisse zu geben; und drittens, wie schnell konvergieren die Cluster auf der Grundlage des vorgeschlagenen zur idealen Lösung? Zusammenfassend lässt sich sagen, dass das Ziel der Experimente darin besteht, die Gültigkeit eines theoretischen Ansatzes zu demonstrieren. Die hier vorgestellten Forschungsergebnisse liefern ausreichenden Nachweis für die Erkennung von sinnvollen Clustern auf der Grundlage von Benutzerinteraktionen. Darüber hinaus zeigen die Experimente deutlich, dass der Non-TI-Clustering-Ansatz als RF-Technik für das Clustering verwendet werden kann.show moreshow less

Download full text files

Export metadata

Additional Services

Search Google Scholar Stastistics
Metadaten
Author: Sanjit Kumar Saha
URN:urn:nbn:de:kobv:co1-opus4-65199
DOI:https://doi.org/10.26127/BTUOpen-6519
Referee / Advisor:Prof. Dr.-Ing. habil. Ingo Schmitt
Document Type:Doctoral thesis
Language:English
Year of Completion:2023
Date of final exam:2023/09/27
Release Date:2023/10/12
Tag:Clustering sozialer Netzwerke; Clustering-Abstand; Relevanz-Feedback
CQQL; Clustering distance; Non-TI clustering; Relevance feedback; Social network clustering
GND Keyword:Social media; Online-Community; Cluster-Analyse; Relevanz-Feedback
Institutes:Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Datenbanken und Informationssysteme
Licence (German):Keine Lizenz vergeben. Es gilt das deutsche Urheberrecht.
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.