TY - THES A1 - Saha, Sanjit Kumar T1 - A relevance feedback approach for social network clustering in the context of triangle inequality violations T1 - Ein Relevanz-Feedback-Ansatz für das Clustering sozialer Netzwerke im Kontext von Dreiecks-Ungleichheitsverstößen N2 - 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 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. N2 - 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 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. KW - Social network clustering KW - CQQL KW - Relevance feedback KW - Non-TI clustering KW - Clustering distance KW - Clustering sozialer Netzwerke KW - Relevanz-Feedback KW - Clustering-Abstand KW - Social media KW - Online-Community KW - Cluster-Analyse KW - Relevanz-Feedback Y1 - 2023 UR - https://opus4.kobv.de/opus4-btu/frontdoor/index/index/docId/6519 UR - https://nbn-resolving.org/urn:nbn:de:kobv:co1-opus4-65199 ER -