User oriented Relation Quality Measurement for Social Networks based on AFC
and CTL
Liwei Zheng
Department of Software Engineering, Computer School
Beijing Information Science and Technology University
No.35 Beisihuan Middle Road, Chaoyang District, Beijing, China
zlw@bistu.edu.cn
Abstract—A social network can be characterized as a system of
mutual relationships between people of some groups. Such
networks are often expressed as graphs. Formal concept let us
have the ability to find good enough relations for a group
based on common properties. But the "quality" of the relations
from Formal concept cannot be measured. That means we just
know the existence of a relation, but we don't know how good
or close of the relation. There must be a method to evaluate the
"quality" of these relations. A relation is good or not might be
decided by the person who cares about it. For different users, a
same relation may be good or not good. So the evaluation of
the "quality" of a relation would be given based on users’
expectation. CTL is used in this paper to define the properties
users caring about. An augmented formal concept is given in
this paper to support the relation discovery on weighted SNS
network. A user oriented relation quality measurement method
is put forward based on CTL and AFC. Using this method, a
quality evaluation could be made from the user's point of view.
(Abstract)
Keywords-SNS; formal concept; CTL; user oritented; relation
quality; measurement (key words)
I. INTRODUCTION
A social network can be characterized as a system of
mutual relationships between people of some groups. Such
networks are often expressed as graphs. These graphs are
always oriented, because the relationship from one person to
another person need not be reciprocal. This kind of graph can
be represented as a classical relation. If S is the set of people,
then the relation R on S should satisfy
.RSSu
Most of the regular relations belonging to R could be
obtained easily based on raw data. What this paper focus on
are the group in which the members might have common
interests or other common properties. The group members
are tightly connected by their common properties.
Here we give an example based on the some sample data
of students' course selection. In this example, there are five
students, Tomas, Jerry, Jake, Rose, and Smith. They will
select some course from five candidate courses. The courses
include traditional culture, math, physics, English and
programming. Table I provides the course selection data of
the five students. From these data, some implicit relation
information could be found.
TABLE I. SAMPLE DATA OF COURSE SELECTION
Traditional
Culture
Math Physics English
Program
-ming
Tomas 1 0 1 0 1
Jerry 0 0 0 0 1
Jake 1 0 1 1 0
Rose 0 1 0 1 0
Smith 0 1 0 0 0
Tomas, Jake, and Smith is a group that they will learn
traditional Culture together. Each two of them will have a
relation and they may meet each other at Monday morning
for the course of traditional culture. If they have more
common courses, their relationship would be tighter because
they may have more together time and more communication.
Formal concept[1-4] was put forward by Ganter and
Wille [1] based on algebraic theory of Galois connections.
The classical formal concept analysis works on Boolean
relationships. There are also some situations where 0/1 does
not describe an examined relationship fully, where more than
two values for characterization of the quality of relationship
are used. So the new question is how to work with attributes
with non-binary values. Some solution is given by Ganter
and Wille in [1] already, namely a scaling: Each many-
valued attribute is decomposed to its binary sub attributes
each of them corresponding to possible value.
Computation tree logic (CTL)[5-8] is a branching-time
logic. Its model of time is a tree-like structure in which the
future is not determined. There are different paths in the
future, any one of which might be an actual path that is
realized. It is often used in formal verification or model
checking. For example, CTL can specify that when some
initial condition is satisfied, then all possible executions of a
program avoid some undesirable condition. In this example,
the safety property could be verified by a model checker that
explores all possible transitions out of program states
satisfying the initial condition and ensures that all such
executions satisfy the property. Computation tree logic is one
kind of temporal logics.
Normally, formal concept is a method to let us have the
ability to find good enough relations for a group based on
common properties. But we cannot get the "quality" of the
relations from Formal concept. That means we just know the
existence of a relation, but we don't know how good or close
2015 Second International Symposium on Dependable Computing and Internet of Things
978-1-5090-0290-0/15 $31.00 © 2015 IEEE
DOI 10.1109/DCIT.2015.25
59