Search results for: clique

Authors: Derkaoui Orkia, Lehireche Ahmed

Abstract:

The topic of this article is to exploring the potentialities of a powerful optimization technique, namely Semidefinite Programming, for solving NP-hard problems. This approach provides tight relaxations of combinatorial and quadratic problems. In this work, we solve the maximum clique problem using this relaxation. The clique problem is the computational problem of finding cliques in a graph. It is widely acknowledged for its many applications in real-world problems. The numerical results show that it is possible to find a maximum clique in polynomial time, using an algorithm based on semidefinite programming. We implement a primal-dual interior points algorithm to solve this problem based on semidefinite programming. The semidefinite relaxation of this problem can be solved in polynomial time.

Keywords: semidefinite programming, maximum clique problem, primal-dual interior point method, relaxation

Procedia PDF Downloads 191

Authors: Yue Yang, Qiang Wu, Xingyu Gao

Abstract:

"Organized research units" have always been an important part of academia. According to the type of organization, there are public research units, university research units, and corporate research units. Existing research has explored the research unit in some depth from several perspectives. However, there is a research gap on the closer interaction between the three from a network perspective and the impact of this interaction on their performance as well as originality. Cliques are a special kind of structure under the concept of cohesive subgroups in the field of social networks, representing particularly tightly knit teams in a network. This study develops the concepts of the diversity of clique types and the diversity of clique geography based on cliques, starting from the diversity of collaborative activities characterized by them. Taking research units as subjects and assigning values to their power in cliques based on occupational age, we explore the impact of clique diversity and clique power on their performance as well as originality and the moderating role of clique relationship strength and structural holes in them. By collecting 9094 articles published in the field of quantum communication at WoSCC over the 15 years 2007-2021, we processed them to construct annual collaborative networks between a total of 533 research units and measured the network characteristic variables using Ucinet. It was found that the type and geographic diversity of cliques promoted the performance and originality of the research units, and the strength of clique relationships positively moderated the positive effect of the diversity of clique types on performance and negatively affected the promotional relationship between the geographic diversity of cliques and performance. It also negatively affected the positive effects of clique-type diversity and clique-geography diversity on originality. Structural holes positively moderated the facilitating effect of both types of factional diversity on performance and originality. Clique power promoted the performance of the research unit, but unfavorably affected its performance on novelty. Faction relationship strength facilitated the relationship between faction rights and performance and showed negative insignificance for clique power and originality. Structural holes positively moderated the effect of clique power on performance and originality.

Keywords: research unit, social networks, clique structure, clique power, diversity

Procedia PDF Downloads 22

Authors: Shahadat Uddin, Md Ekramul Hossain, Arif Khan

Abstract:

The collaboration among physicians during episodes of care for a hospitalised patient has a significant contribution towards effective health outcome. This research aims at improving this health outcome by analysing the attributes of patient-sharing physician collaboration network (PCN) on hospital data. To accomplish this goal, we present a research framework that explores the impact of several types of attributes (such as clique and clan) of PCN on hospitalisation cost and hospital length of stay. We use electronic health insurance claim dataset to construct and explore PCNs. Each PCN is categorised as ‘low’ and ‘high’ in terms of hospitalisation cost and length of stay. The results from the proposed model show that the clique and clan of PCNs affect the hospitalisation cost and length of stay. The clique and clan of PCNs show the difference between ‘low’ and ‘high’ PCNs in terms of hospitalisation cost and length of stay. The findings and insights from this research can potentially help the healthcare stakeholders to better formulate the policy in order to improve quality of care while reducing cost.

Keywords: clique, clan, electronic health records, physician collaboration

Procedia PDF Downloads 117

Authors: A. Melka, N. Slater, A. Mualem, Y. Louzoun

Abstract:

Networks are often presented as containing a “core” and a “periphery.” The existence of a core suggests that some vertices are central and form the skeleton of the network, to which all other vertices are connected. An alternative view of graphs is through communities. Multiple measures have been proposed for dense communities in graphs, the most classical being k-cliques, k-cores, and k-plexes, all presenting groups of tightly connected vertices. We here show that the edge number thresholds for such communities to emerge and for their percolation into a single dense connectivity component are very close, in all networks studied. These percolating cliques produce a natural core and periphery structure. This result is generic and is tested in configuration models and in real-world networks. This is also true for k-cores and k-plexes. Thus, the emergence of this connectedness among communities leading to a core is not dependent on some specific mechanism but a direct result of the natural percolation of dense communities.

Keywords: cliques, core structure, percolation, phase transition

Procedia PDF Downloads 135

Authors: Ho Yeon Park, Kyoung-Jae Kim

Abstract:

The purpose of this study is to investigate whether friendship in social media can be an important factor in recommender system through social scientific analysis of friendship in popular social media such as Facebook and Twitter. For this purpose, this study analyzes data on friendship in real social media using component analysis and clique analysis among sub-group analysis in social network analysis. In this study, we propose an algorithm to reflect the results of sub-group analysis on the recommender system. The key to this algorithm is to ensure that recommendations from users in friendships are more likely to be reflected in recommendations from users. As a result of this study, outcomes of various subgroup analyzes were derived, and it was confirmed that the results were different from the results of the existing recommender system. Therefore, it is considered that the results of the subgroup analysis affect the recommendation performance of the system. Future research will attempt to generalize the results of the research through further analysis of various social data.

Keywords: sub-group analysis, social media, social network analysis, recommender systems

Procedia PDF Downloads 323

Authors: Charles Mazhazhate

Abstract:

This study interrogates and analyses the intricate kin- and- kith network patterns of corruption and mismanagement of resources prevalent in public sector supply chains bedeviling the developing economies of Sub-Saharan Africa with particular reference to Zimbabwe. This is forcing governments to resort to harsh fiscal policies that see their citizens paying high taxes against a backdrop of incomes below the poverty datum line, and this negatively affects their quality of life. The corporate world is also affected by the various tax-regime instituted. Mismanagement of resources and corrupt practices are rampant in state-owned enterprises to the extent that institutional policies, procedures, and practices are often flouted for the benefit of a clique of individuals. This interwoven in kith and kin blood human relations in organizations where appointments to critical positions are based on ascribed status. People no longer place value in their systems to make them work thereby violating corporate governance principles. Greediness and ‘unholy friendship connections’ are instrumental in fueling the employment of people who know each other from their discrete backgrounds. Such employments or socio-metric unions are meant to protect those at the top by giving them intelligent information through spying on what other subordinates are doing inside and outside the organization. This practice has led to the underperforming of organizations as those employees with connections and their upper echelons favorites connive to abuse resources for their own benefit. Even if culprits are known, no draconian measures are employed as a deterrence measure. Public value along public sector supply chains is lost. The study used a descriptive case study research design on fifty organizations in Zimbabwe mainly state-owned enterprises. Both qualitative and quantitative instrumentations were used. Both Snowball and random sampling techniques were used. The study found out that in all the fifty SOEs, there were employees in key positions related to top management, with tentacles feeding into the law enforcement agents, judiciary, security systems, and the executive. Such employees in public seem not to know each other with but would be involved in dirty scams and then share the proceeds with top people behind the scenes. The study also established that the same employees do not have the necessary competencies, qualifications, abilities, and capabilities to be in those positions. This culture is now strong that it is difficult to bust. The study recommends recruitment of all employees through an independent employment bureau to ensure strategic fit.

Keywords: corruption, state owned enterprises, strategic fit, public sector supply chains, efficiency

Procedia PDF Downloads 132