_K_ eywords mobile phone data; call detail records; type allocation code; data
analysis; human mobility; urban mobility; social sensing; socioeconomic
status; circadian rhythm; sleep wake cycle

# Awakening City: Traces of the Circadian Rhythm within the Mobile Phone
Network Data

Gergő Pintér
John von Neumann Faculty of Informatics,
Óbuda University,
Bécsi út 96/B, 1034 Budapest, Hungary
<EMAIL_ADDRESS>&Imre Felde
John von Neumann Faculty of Informatics,
Óbuda University,
Bécsi út 96/B, 1034 Budapest, Hungary
<EMAIL_ADDRESS>0000-0003-4731-3816 0000-0003-4126-2480

###### Abstract

In this study, Call Detail Records (CDR), covering Budapest, Hungary has been
processed to analyze the circadian rhythm of the subscribers. An indicator,
called wake-up time, is introduced to describe a behavior of a group of
subscribers. It is defined as the time, when the mobile phone activity of a
group rises in the morning. Its counterpart is the time, when the activity
falls in the evening. Inhabitant and area-based aggregation are also
presented. The former is to consider the people who live in an area, the
latter uses the transit activity in an area to describe the behavior of a part
of the city. The opening hours of the malls and the nightlife of the party
district was used to demonstrate this application, as real-life examples. The
proposed approach was also used to estimate the working hours of the
workplaces. The findings are in a good agreement with practice in Hungary, and
also support the workplace detection method. Negative correlation was found
between wake-up time and mobility indicators (Entropy, Radius of Gyration): On
workdays, people wake up earlier and travel more, on holidays it is quite the
contrary. The wake-up time was evaluated in different socioeconomic classes,
using housing prices and mobile phones prices, as well. It was found that
lower socioeconomic groups tend to wake up earlier.

##  1 Introduction

The mobile phone network, during its operation, constantly communicates with
the cell phones. This communication can be divided into two categories: (i)
the passive, cell-switching communication, that keeps the cell phones ready to
use the mobile phone network at any time, and (ii) the active, billed usage of
the mobile phone network, including phone calls, text messages or mobile
internet usage. The Call Detail Records (CDR) collect the latter, containing
information about the subscriber, the time of the activity and the place (via
the cell), where the activity is occurred.

In the last few decades, anonymized CDR have become a standard information
source for analyzing the characteristics of human mobility. The billed
activities of the subscribers are recorded, providing information about the
whereabouts of the population. The human mobility analysis, based on this
massive information source, is utilized in fields — among others — like social
sensing, epidemiology, transportation engineering, urban planning or
sociology. Furthermore, human sleep wake cycle (SWC) is also studied by
analyzing mobile phone network data.

CDR processing is often applied for large social event detection, such as
football matches [52, 58, 33, 43], concerts [35], sociopolitical events [20,
25] or mass protests [45, 48]. Epidemiology is used to be mentioned as a
potential application of human mobility studies, but the COVID-19 pandemic
prioritized its applications in Digital Epidemiology, as mobile phone network
data can reflect the mobility changes, caused by the imposed restrictions.
Willberg et al. found a considerable decrease of the population presence in
the largest cities of Finland, after the lockdown [57]. Romanillos et al.
reported similar results from the Madrid metropolitan area [47]. Lee et al.
examined the mobility changes during the lockdown in England, and found that
the mobility of the wealthier subscribers decreased more significantly [17].
Khataee et al. compared the effect of the social distancing in several
countries, using mobility data from Apple phones [29]. Bushman et al. [10],
Gao et al. [21], Hu et al. [26] and Tokey [51] also analyzed effects of the
stay-at-home distancing on the COVID-19 increase rate, in the US. Lucchini et
al. studied the mobility changes during the pandemic, in four US states [32].

Identifying the home and work locations of a subscriber is a common [42, 60,
27, 54, 59, 63, 34, 41, 44] and crucial part of the CDR processing, as these
locations fundamentally determine the people’s mobility customs. Furthermore,
a good portion of the people live their lives in an area, that is determined
by only their home and workplace [42, 27] or their communities [22]. Using the
home and the work locations, the commuting trends can be analyzed [13, 30, 63,
34, 44].

Analyzing city structure led to the analyses of the socioeconomic structure of
the population, as different social classes live in different parts of a city,
but CDR s also have been used to analyze gender and minority segregation [23].
Xu et al. [59] used six mobility indicators, housing prices and per capita
income in Singapore and Boston to analyze the socioeconomic classes. It was
found that the wealthier subscribers tend to travel shorter distances in
Singapore, but longer, in Boston. Barbosa et al. also found significant
differences in the average travel distance between the low and high income
groups in Brazil [8]. In a previous work, we have also demonstrated
differences in mobility customs between socioeconomic classes [44], in the
case of Budapest. Ucar et al. revealed socioeconomic gap by mobile service
consumption [53]. Vilella et al. found that education and age play news media
consumption patterns, in Chile, using a dataset, that provides information
about the visited websites [56].

The studies, cited before, mainly focus on the spatial distance between the
home and work locations, as it is hard to estimate the travel time, using
sporadic CDR data, though it has seasonal nature due to the human biorhythm.
Moreover, human mobility is highly regular [24, 50], and the individual
activity has a bursty characteristic [7]. Jo et al. found that removing the
circadian and weekly seasonality, the bursty nature of the human activity
remains [28].

In the digital era, the human sleep wake cycle (SWC) is also studied using the
info-communication systems, such as smartphones [14, 5], websites [62, 61,
56], social media [18] and call detail records (CDR) [1, 28, 6, 31, 36, 37,
4]. Cuttone et al. used screen-on events of the smartphones to study the daily
sleep periods [14], and Aledavood et al. examined the social network of
different chronotypes, using the same data set [5]. Monsivais et al.
identified yearly and seasonal patterns in calling activity and resting
periods [36, 37]. Lotero et al. found connection between temporal patterns and
the socioeconomic status of the subscribers, namely the wealthier wakes up
later [31]. Diao et al. found difference in the daily activity between
different districts of Boston [15].

Economic models distinguish city parts such as residential areas, industrial
areas, business districts and so on, but that is a rather static, slowly
evolving layer of a city. Mobile phone network data has a potential to
describe the city structure, via the inhabitants’ mobility patterns. This
study focuses on the effect of the SWC to the city structure. In this regard,
it is a continuation of our previous work [44], but this time, the city
structure is analyzed by the circadian rhythm of the people who live and work
in a given area of the Budapest.

Is it possible to cluster the areas of a city by time, when the activity of
the inhabitants, the workers, or the passers-by start their activity in the
morning or halt in the evening? Do city parts have “chronotypes”? Can
neighborhoods or districts be described by the terms “morningness” or
“eveningness”? Is there a structural or socioeconomic connection between the
areas with the same “chronotype”?

The goal of this study is to answer these questions, and the contributions of
this paper are briefly summarized as follows:

  1. 1.

Introducing wake-up time as an indicator to describe the behavior of a group
of subscribers.

  2. 2.

Using this indicator to distinguish the areas of Budapest.

  3. 3.

Estimating the day length and the working hour length, using the same method.

  4. 4.

Demonstrating connection between the wake-up time and the mobility customs.

  5. 5.

Identifying correlation between the wake-up time and the socioeconomic status.

The rest of this paper is organized as follows. The utilized data are
described in Section 2; then, in Section 3, the applied methodology is
introduced and in Section 4 the results of this study are presented and
discussed. Finally, in Section 5, the findings of the paper are summarized,
and a conclusion is drawn.

##  2 Materials

Vodafone Hungary, one of the three mobile phone operators providing services
in Hungary, provided two anonymized CDR data sets for this study. The
observation area was Budapest, the capital of Hungary and its agglomeration.
Both observation periods are one month long, the first is June 2016, the
second is April 2017. The nationwide market share of Vodafone Hungary was
25.3% in 2016 Q2, and 25.5% in 2017 Q2 [38].

The communication between a cellular device and the mobile phone network can
be divided into two categories: (i) An administrative communication
maintaining the connection with the service, for example, registration of the
cell-switching that can be called passive communication. (ii) When the device
actively uses the network for voice calls, message or data transfer, that can
be called active communication. The available data contains only the active
communication, which is sparser, so it cannot be used to track continuous
movements.

The obtained data contains a hashed value to identify the SIM (Subscriber
Identity Module), a timestamp that is truncated to 10 s, and an ID of the
cell. Thus, a subscriber can be mapped to a geographic location in a given
time. These are extended with the type of the customer (business, consumer),
the type of the subscription (prepaid, postpaid), the age and gender of the
subscriber and the Type Allocation Code (TAC) of the device. The TAC is the
first eight digits of the IMEI (International Mobile Equipment Identity)
number, and allocated by the GSM Association and uniquely identifies the
mobile phone model. These values are also present in every record, so for
example the device changes can be tracked as well.

Both the type of the activity (voice call, message, data transfer) and the
direction (incoming, outgoing) were omitted from the data, and there was no
data provided by the operator to resolve the TAC s to manufacturer and model.

The data was processed using the same framework as in out previous works [44,
43]. During the data cleaning process, the wide format was normalized. The CDR
table contained only the SIM ID, the timestamp, and the cell ID. For the
subscriber and subscription related information, a separate table was formed,
and another table was created to track the device changes of the subscriber.

Another table has been created for the cell information, including a cell ID,
the geographic location of the cell centroid and base station. The cell
centroid is an estimation based on a momentary state, especially with the UMTS
cells, that apply a load balancing mechanism, called “cell breathing”, which
can change the geographic size of the serving area. The heavily loaded cells
shrink, and the neighboring ones grow to compensate [3].

###  2.1 June 2016

This data set includes $2291246932$ records from $2063005$ unique SIM cards,
during the observation period of June 2016. Figure 1 shows the activity
distribution between the activity categories of the SIM cards. The dominance
of the last category, SIM cards with more than 1000 activity records, is even
more significant. It can be seen that almost 27% of the SIM cards produce more
than 91% of the total activity.

Figure 1: The SIM cards, in the “June 2016” data set, categorized by the
number of activity records. The SIM cards with more than 1000 activity records
(26.98% of the SIM cards) provide the majority (91.31%) of the activity.

Figure 2 shows the SIM card distribution according to the number of active
days. Only 34.59% of the SIM cards had activity on at least 21 different days.
In total, $241824$ SIM cards (11.72%) appeared on at least two days, but the
difference between the first and the last activity was not more than seven
days. This may indicate the presence of tourists. High levels of tourism are
usual during this part of the year.

Figure 2: SIM card distribution of the “June 2016” data set, by the number of
active days.

Type Allocation Codes are provided for every record because a subscriber can
change their device at any time. Naturally, most of the subscribers ($95.71$%)
used only one device during the whole observation period.

While the subscription details were available for every SIM card, the
subscriber information was missing in slightly more than 40% of the cases,
presumably because of the subscribers’ preferences regarding the use of their
personal data.

Although the data contained cell IDs, only the base station locations, where
the cell antennas were located, were known. As a base station usually serve
multiple cells, these cells were merged by the serving base stations. After
the merge, 665 locations (sites) remained with known geographic locations. To
estimate the area covered by these sites, Voronoi Tessellation was performed
on the locations. This is a common practice [13, 40, 55, 63, 39] in CDR
processing.

###  2.2 April 2017

The second CDR data set contains $955035169$ activity records, from $1629275$
SIM cards, and the observation period is April 2017. Figure 3, shows the
activity distribution between the activity categories of the SIM cards. Only
17.67% of all the SIM cards, that have more than 1000 activity records,
provide the majority (75.48%) of the mobile phone activity during the
observation period. Figure 4, shows the distribution of the SIM cards by the
number of active days. Only about one-third (33.23%) of the SIM cards have
activity on at least 21 different days. In spite of the relatively large
number of SIM cards, present in the data, most of them are not active enough
to provide enough information about their mobility habits. Figure 5a, shows
the mobile phone network activity distribution during the observation period,
and Figure 5b its Fourier decomposition to highlight the seasonality of the
data. As expected, this 30-day dataset has a 24-hour periodicity. In this
study, mainly this data set was used, the “June 2016” is only used as a
reference for some analyses (e.g., in Section 4.2).

Figure 3: The SIM cards in the “April 2017” data set categorized by the number
of activity records. The SIM cards over a thousand records (17.7%) provide the
majority (75.48%) of the activity. Figure 4: SIM card distribution of the
“April 2017” data set, by the number of active days.

(a)

(b)

Figure 5: The mobile phone network activity (a) during the observation period
of April 2017, and its Fourier decomposition (b).

###  2.3 Data for the Socioeconomic Indicators

In a previous work [44], real estate prices a were used to characterize the
socioeconomic status. The ingatlan.com estate selling website provided more
than 60 thousand estate locations with floor spaces and selling prices from
Budapest and Pest county. These prices were used to describe the property
prices at the subscribers’ home locations. Figure 6(a), shows the distribution
of the normalized housing prices from the advertisements.

Our former paper [43] was focusing on the price and the relative age of the
subscribers’ mobile phone were utilized as a socioeconomic indicator. The
data, used for resolving the TAC s to hardware vendor and model, was provided
by 51Degrees. With the model and type of the device, in which the SIM cards
operate, can also be used to remove those SIM cards, that is not used in
mobile phones, thus do not represent a human. The cell phone prices and the
release dates were obtained from GSMArena [49]. The relative age of a phone is
determined as the difference of the date of the CDR data set (e.g., April
2017) and the release date of the phone. Figure 6(c), shows that most of the
devices are one to three years old, but there are some really outdated (over
eight years) phones in use. Figure 6(b), displays the distribution of the cell
phone prices. Although, the data source is supposed to contain launch prices,
the validation analyzes (Appendix B) implies that the phone prices are
depreciated.

(a)

(b)

(c)

Figure 6: Distribution of the real property prices (a), the mobile phone
prices (b), and the mobile phone relative ages (c).

##  3 Methodology

In In a previous work [44], a framework was introduced to process the mobile
phone network data, described in Section 2. The CDR s were normalized, cleaned
and the mobility metrics (Section 3.2) were determined for every subscriber.

###  3.1 Home and Work Locations

Most of the inhabitants in cities spend significant time of a day at two
locations: their homes and work places. In order to find the relationship
between these most important locations, first their positions of these
locations have to be determined. There are a few approaches used to find home
locations via mobile phone data analysis [2, 60, 54, 34, 41].

Our solution is similar to the most common approach. The most frequent cell
where a SIM card is present during working hours is considered as the work
location, on workdays between 09:00 and 16:00. The home location is calculated
as the most frequent cell where a SIM card is present during the evening and
the night on workdays (from 22:00 to 06:00) and all day on holidays. Although
people do not always stay at home on the weekends, it is assumed that a
significant amount of activity is generated from their home locations. In
[44], we used census data to indirectly, via commuting trends, validate the
estimated home and work locations.

###  3.2 Mobility Metrics

Along with the Home and Work locations, the Radius of Gyration and the Entropy
are commonly used [42, 40, 59, 12, 34, 9, 44, 32] indicators of human
mobility, and were also determined for every subscriber.

The Radius of Gyration [24] is the radius of a circle in which an individual
(represented by a SIM card) can usually be found. It was originally defined in
Equation (1), where $L$ is the set of locations visited by the individual,
$r_{cm}$ is the center of mass of these locations, and $n_{i}$ is the number
of visits to the i-th location.

$r_{g}=\sqrt{\frac{1}{N}\sum_{i\in L}{n_{i}(r_{i}-r_{cm})^{2}}}$ (1)

The entropy characterizes the diversity of locations visited using an
individual’s movements, defined as Equation (2), where $L$ is the set of
locations visited by an individual, $l$ represents a single location, $p(l)$
is the probability of an individual being active at a location $l$, and $N$ is
the total number of activities taken part in by an individual [40, 12].

$e=-\frac{\sum_{l\in L}{p(l)\log p}}{\log N}$ (2)

###  3.3 Wake-up Time

Figure 7: Calculation of the wake-up and the bedtimes

The Call Detail Records are aggregated for every cell and 10 minute time
intervals. Then, moving average is applied with the window of 12. The minimum
of the aggregated records is usually in the middle of the night, and the
maximum is in the afternoon. To determine the wake-up time, the positive edge
of the curve needs to be detected, when the number of the mobile phone
activity increases drastically in a short period of time. The time, that is
considered as the wake-up time, is simply where the activity value reaches the
mean of the minimum and the maximum of the curve. Figure 7, illustrates the
concept. Equation 3, defines the mean of the activity edge, where $a_{min}$
and $a_{max}$ is the minimum and the maximum of the (daily) activity level,
respectively.

$m=(a_{max}-a_{min})*0.5+a_{min}$ (3)

This process is repeated for every day, then the median of the daily wake-up
times are determined. Analogously to the wake-up time, the bedtime can be
calculated to describe when the mobile phone activity decreases significantly,
as selecting the mean value on the negative edge. It has to be noted, that
these values are naturally not the actual times when people wake up or fall
asleep. Those moments cannot be determined using simply the mobile phone
network. Using the screen-on events of the phone [14] can be much closer to
the actual values. Especially in the case of the wake-up time, if the phone is
used as an alarm clock. In spite of this, it is supposed that this
approximating method can reveal the rough tendencies of the daily routine.
Still, the terms “wake-up time” and “bedtime” are used to refer to the time of
the positive/rising and negative/falling edges of the daily activity curve,
respectively.

###  3.4 Aggregation of the Subscribers

As the type of the phone activity is unknown, the wake-up time of the
individual is hard to estimate. Since making a call requires to be awake
(whereas message could be received and data could be transferred
autonomously), knowing which activities represent phone calls would provide
more accurate information about when people are certainly awake. Instead of
this, the significant activity increase is to be used to identify the wake-up
time.

Furthermore, activity of a single device is also sporadic and does not provide
enough data to identify an activity increase for every day. To mitigate the
downside of the sporadic nature of the data, the devices are grouped, that can
be performed in two ways: (i) calculate the wake-up time of an area (a cell or
a group of cells) or (ii) the inhabitants of an area.

In the first approach, the activity records are aggregated that takes place in
a given cell, regardless which SIM cards produce them. In the case of the
second version, those activity records are used, that produced by the
inhabitants of the given cell, regardless where the activity took place. The
first approach could be called cell-based grouping and the latter inhabitant-
based grouping. The two approaches are illustrated in Figure 8. Cells can be
grouped further to examine a larger area (residential, suburb, district,
etc.).

(a)

(b)

Figure 8: Visualizing the difference between the cell-based (a) and the
inhabitant-based (b) approaches. The former considers subscribers present in a
given cell wherever they live. The latter aggregates activity of the
inhabitants to the home cell, regardless where the activity occurred.

##  4 Results and Discussion

In this section, the results have been summarized and discussed, and the
limitations and the future work has been included.

###  4.1 Inhabitant-based Approach

Based on the results of the “April 2017” data set (Figure 9(a) and 9(b)), the
wake-up time almost always around 7:10 on workdays. On Sundays (or Easter
Monday in the case of the long holiday), it is later by about one hour. On
Saturdays (and the other days of the holiday), it is later by about 30–40
minutes compared to an average workday.

The bedtimes are not so even, but also have a nice trend. The activity
decreases between 19:40 and 20:10, on workdays, but the holiday values shifted
by 30–50 minutes, similarly to the wake-up times. Interestingly, as bedtimes
follows the wake-up times on the weekends, it results that the average day
length remains approximately the same. Figure 9(c), shows the day lengths,
calculated as a difference of the bedtime and the wake-up time, in minutes.
The day lengths are between 12 hours 30 minutes and 13 hours 10 minutes. In
average, the day length is 12 hours 45 minutes (the standard deviation is 10
minutes).

The same evaluation has been performed on the “June 2016” data set. Figure
9(d) and 9(e), show the daily wake-up times and bedtimes, respectively.
Basically, the same tendencies can be observed: wake-up times and bedtimes are
shifted on holidays. However, there are some irregularities, especially within
the bedtimes. On June 22, the bedtime is almost on the same level as a
weekend. The mobile phone activity decrease occurred 30 minute later than on
the other days of that week.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 9: Daily wake-up times (a,d), bedtimes (b,e), and the day lengths
(c,e), for the “April 2017” (a–c) and the “June 2016” (e–e) dataset. Holidays
are represented by a different color. Figure 10: Inhabitant-based wake-up
(brown) and bedtime (green) values of the cells, April 2017.

Figure 10, displays the inhabitant-based wake-up and bedtimes of the cells.
This result is comparable to [14, Figure 9], however in that case, the wake-up
times ($t_{wake}$) were earlier and bedtimes were later ($t_{sleep}$). Note
that, the difference ensue from the nature of the approach. In [14], the
screen-on events of the phones are considered, while in Figure 10, the active
usage of the mobile phone network is aggregated for a larger area. The
“SensibleSleep” application [14] observes offline (from a mobile phone network
perspective) smartphone activity, that adjusts better to the actual SWC of an
individual.

###  4.2 The Length of the Day

Figure 9(a) and 9(b), show that people start and end their days later on the
holidays. This makes perfect sense, hence they do not need to go to work, they
do not need to spend time with traveling to get somewhere in time, and they
probably like to rest more. But, the bedtime is shifted as well, this results
that the length of the day is remains practically the same, see Figure 9(c).

Although, the two data sets (Section 2.1 and 2.2) were not recorded in the
same year, but still covers two different months of a year (April and June).
Considering that a mid-spring month is well represented by the “April 2017”
dataset, and an early summer month by the “June 2016” dataset (for Budapest),
the differences between the wake-up time, bedtime, and the day length can be
compared between two seasons.

Figure 9(d), shows a small increase in the wake-up times, during the second
half of the month. Although, that 10-minute increase in the averages cannot be
considered significant, it may reflect the end of the school term (June 15).
During the intersession, the time schedule of the public transport services is
adjusted. For many lines, the headway is increased on workdays, while for some
lines, it is decreased, especially on weekends. In this way, the intersession
affects the whole transportation system of Budapest, and even its
agglomeration to some extent.

(a)

(b)

Figure 11: Sunrise (a) and sunset (b) times of June 2016 and April 2017
projected to the same figure to highlight the differences between the seasons,
using data from [11].

Until the summer solstice (June 20 in 2016 [19]), the days are getting longer,
but can the longer daylight have en effect to mobile phone network activity?
As a reference, astronomical information (sunrise and sunset) has obtained
from www.visualcrossing.com [11] for Budapest. Figure 11, shows the difference
between the sunrises and the sunsets during the two observation periods of the
data sets, projected to the same figure. The dashed lines display the values
of June, and the solid lines display the values of April. As the summer
solstice is in June, the differences during the month are negligible, but in
April, the differences between the beginning and the end of the month are much
more significant.

So, in June, the Sun rises earlier and sets later than in April, consequently
lighter period of days are longer. June 15 is more than 2-hour longer than
April 15, using the astronomical definitions of the sunrise and sunset.
According to the calculated day lengths, the average workday length is 12
hours in the “June 2016” data set, and 10 hours and 40 minutes in the “April
2017” data set, resulting a difference of the 80 minutes.

Although, this is less than the astronomical difference, but the Sun rises
very early in the morning, when people are still sleeping. It may be more
practical to compare the results with the difference of the sunsets. As, the
people do not wake up earlier just to organize an activity before work, but
may do after work if it is still bright and the weather is good. The Sun sets
at 19:33 on April 15 and at 20:42 on June 15, that is a 69-minute difference,
that is more comparable to the calculated values. The average workday bedtime
values are 19:43 and 20:47, respectively. This finding — the day lengths are
longer in June — is in good agreement with [36], where the seasonal influence
of the daylight was examined via the length resting period.

The wake-up times are 8:57 and 8:44 in average (workdays), that show a slight
decrease in the summer. Figure 9(d), shows slightly later wake-up times in the
second half of the month. The average workday wake-up time in the first half
of June 2016 is 8:39, and 8:50 in the second half. As mentioned in Section
4.1, it might be caused by the end of the school term.

###  4.3 Area-based Approach

Based on the cell/area activity, the wake-up, and the bedtime has been
determined for every cell. Figure 12(a) and 12(c), show the distribution for
workdays, and Figure 12(b) and 12(d), show distribution for holidays,
respectively. The results clearly show that the usage of the mobile phone
network intensifies and reduces later on the holidays, indicating the people
wake up and go to sleep later when they do not work.

(a)

(b)

(c)

(d)

Figure 12: Cell based wake-up (a, b) and bedtime (c, d) distribution for
workdays and holidays, respectively, in the “April 2017” dataset. Figure 13:
Spatial distribution of the cell-based wake-up times, malls (1-8) opens at
10:00. Figure 14: Spatial distribution of the cell-based bedtimes, aggregated
to sites.

Figure 13, shows the spatial distribution of the cell-based wake-up times. The
Voronoi polygons, representing the mobile phone cells, are colored by the
calculated “wake-up” times. The map clearly shows some extrema, where the
times are around 10:00. Extrema 1-8 are all malls (WestEnd City Center (1),
Arena Mall (2), Árkád (3), KÖKI Terminál (4), Lurdy Ház (5), Allee (6), MOM
Park (7) and Mammut (8).), that uniformly open at 10:00, though 5 and 8 partly
serves as office buildings.

Figure 14, shows the bedtime values of the sites, on workdays. As the Figure
12(c), illustrates in respect of cells, the bedtime is usually between 20:00
and 22:00. There are, however, a some sites with later bedtime, a few of them
are denoted in the figure. Marker 1 at the party district (Appendix A). In the
site at marker 2, does not have any distinctive object, that could explain
this result. However, East of that site, there is a beer factory, that might
have notable activity in the evening — compared to the neighborhood — and the
distortion of the Voronoi tessellation could have resulted this late bedtime.
At marker 3, there is a student’s hostel and, in the neighborhood, there are
some sport and concert venues.

###  4.4 Working Hours

Figure 15, shows the activity distribution by days of week and hours, based on
the “April 2017” data set, separating the workplace (15(a)) and the home
(15(b)) activity, but using the same scale. At the workplace, most of the
activity recorded during the working hours on workdays, as expected. The
activity increases fast in the mornings, but decreases more slowly in the
afternoon. The home activity was the mostly clustered on the weekends, but
after the work hours, in the evening, had a notable activity peak. The home
activity before the working hours does not seem so significant.

This procedure can be applied for every cell (or group of cells, like sites),
then the activity of the workers and the inhabitants will represent the
workplace and home activity tendencies. Note that, a cell can have both
workers and inhabitants, so every cell have two aspects. Figure 16(a) and
16(b), illustrates the activity of the subscribers who work and live a
selected site, respectively. Figure 16(a), also demonstrates the concept of
Figure 7, using actual data.

As expected, Figure 16(a) and 16(b) is in accord with Figure 15(a) and Figure
15(b). Workers’ activity increases in the morning and decreases late in the
afternoon, whereas the inhabitants’ activity decreases in the morning and
increases late in the afternoon and reaches its peak in the evening. The two
aspect of the same site has the opposite tendency.

(a)

(b)

Figure 15: The mobile phone activity distribution by days of week and hours
based on the “April 2017” data set, for the work places (a) and the homes (b).

Applying the same, inhabitant-based approach as in the case of the wake-up
time (Figure 7) to the workers’ activity, it is possible to detect the
positive and the negative edge of the activity curve. The positive edge could
indicate the start of the working hours, and the negative edge could indicate
the end of the working hours in a given cell (or site). Moreover, the
difference of the two times can determine the length of the working hours.

In most of the sites, the working hours are about 8 hours (Figure 17), just as
expected. In the rest of the sites, — especially where the working hour is
less than 7 hours or over 9 and a half hours — the mobile phone activity
proved to be so low during the working hours, that the results cannot be
considered appropriate. Nevertheless, the mobile phone network reflects the
length of the working hours.

The work hours do not necessarily start and end at the same time in every
workplace. Are there any differences in this regard, from a mobile phone
perspective?

(a)

(b)

Figure 16: Activity of the workers (a) and the inhabitants (b) of a selected
site, on a selected day.

Figure 17, shows the average workday length of the sites. The workday length
in most of them are around eight hours, that agrees with the practice, in
Hungary. Moreover, the distribution of the working hour lengths also verifies
the workplace detection approach, summarized in Section 3.1. Although, there
are some sites with very low (less than seven hours) or high (more than nine
and a half hours), but these sites have very few activities during the
observation period: less than 2% of the total activity occurs in these sites.

The length of the working hours is usually around eight hours in most of the
sites, but there might be differences at the beginning and the end of the
labor-time. Figure 18(b), shows the five most frequent beginning and ending
labor-time (defined as the positive and negative edge of the workplace
activity curve of the site) and the connection between them, using a type of
Sankey diagram. It is clear, that in most of the sites, the mobile phone
network activity increases between 8:30 and 9:30. The most notable group That
is not surprising, considering he lunch break. Note that, the observed time
values may have a delay compared to the actual start of the work. As an
employee may not actively use the mobile phone network as soon as they arrived
to their workplace (or when they left it).

Figure 17: Distribution of workday length in sites.

(a)

(b)

Figure 18: The distribution of the starting (brown) and the ending (green) of
the working hours, in sites (a); and the connection between the starting and
the ending times (b).

###  4.5 In Respect of Mobility

In [44], we also showed that the mobility has a weekly seasonality. As Figure
9 shows, the wake-up time also have a seasonality. To compare it with the
mobility indicators, described in Section 3.2, the daily wake-up times and the
mobility metrics were normalized, using min-max feature scaling. Figure 19a
and Figure 19b, displays the normalized Entropy and the normalized Radius of
Gyration — without the non-phone devices — in contrast of the wake-up times,
respectively. As the mobility indicators are determined per subscriber, the
inhabitant-based version of the wake-up time is used.

During workdays, both the Entropy and the Radius of Gyration were high, but
the wake-up time was low. On holidays, it is on the contrary, the wake-up
times were higher, the mobility indicators were lower. This is not surprising,
hence people tend to wake up earlier on workdays to go to work, thus people
usually need to travel to their workplace. On holidays, it is common to spend
more time at home, that also reduces the mobility values. Figure 19,
visualizes this clearly, especially in the case of Entropy. Numerically
(Pearson’s R), the correlation between the wake-up times and the mobility
indicators (Entropy, Radius of Gyration) are $-0.8932$ and $-0.6873$,
respectively.

Bedtimes show a similar trend (Figure 19c and Figure 19d) in contrast of the
two mobility metrics (Entropy and Radius of Gyration), however, the
correlations numerically are not that strong: $-0.85$ and $-0.6621$,
respectively. This might have caused by leisure activities, after work. While
people may go straight to work in the morning, they do not necessarily go home
right after work.

(a)

(b)

(c)

(d)

Figure 19: Normalized, inhabitant-based wake-up times in contrast of the
normalized daily Entropy (a) and Radius of Gyration (b). Pearson’s Rs are
$-0.8932$ and $-0.6873$, respectively. Second row: Normalized, inhabitant-
based bedtimes in contrast of the normalized daily Entropy (c) and Radius of
Gyration (d). Pearson’s Rs are $-0.85$ and $-0.6621$, respectively.

###  4.6 In Respect of Socioeconomic Status

In an earlier work [44], we demonstrated correlation between the mobility
customs, the distance of the home and work locations and the socioeconomic
status. We found that people who live in less expensive parts of Budapest,
tend to travel more to their workplace. The larger distance should indicate
longer travel times and earlier wake-up times, as the work mostly starts at
the same time in the morning. Lotero et al. previously found that “rich people
do not rise early” [31], analyzing two cities of Colombia.

As for Budapest, there is a positive correlation between the socioeconomic
status and the wake-up time. The inhabitant-based approach is used for this
analysis, as the socioeconomic indicators are applied to subscribers. Besides
the real estate prices [44], two properties of the mobile phones [43] were
considered: the price and relative age. Figure 20a, shows the wake-up times in
contrast of the real property price and the mobile phone price categories. To
give context to these categories, Figure 20b illustrates the number of
subscribers in each category. Figure 21, has the same structure, but applying
to the age of the cell phones.

Four property price categories and five phone price categories are formed. As
Figure 6a, shows most of the price of one square meter in most of the real
estate advertisements are under 0.6 million HUF. The property price categories
are: (i) 0.3–0.5, (ii) 0.5–0.7, (iii) 0.7–0.9 and (iv) 0.9–1.3 million HUF.
Mobile phone price categories are: (i) 0–150, (ii) 150–300, (iii) 300-450,
(iv) 450–600 and (v) 600–750 EUR. As for the mobile phone age, five categories
were formed from 0 to 5 years. The older phones were omitted. As Figure 6,
indicates most of the subscribers lived in less expensive homes and used less
expensive cell phones, that were 1 to 3 years old.

In Figure 20a, the wake-up times are increasing in both dimensions. The lowest
wake-up value is in the top-left corner, where the owners of the least
expensive home locations and cell phones are grouped. Towards the bottom-right
corner, the wake-up times are increasing. This observation clearly indicates
that, the richer people start their days somewhat later than the less wealthy
people. The differences are numerically not large between the categories, but
the observation area is also relatively small. Budapest is 525 square
kilometers, and its diameter is about 30 km. The farthest part of the
agglomeration is about 40 km from the city center.

Figure 21a, reveals negative correlation between phone age and the wake-up
time. This result implies that wealthier people do not only use more expensive
phones, but tend to use the latest models. Presumably, they replace their
phones more often.

(a)

(b)

Figure 20: The inhabitant-based wake-up times in the socioeconomic categories,
based on the property price of the home location and mobile phone price (a),
and the number of the subscribers in each category (b).

(a)

(b)

Figure 21: The inhabitant-based wake-up times in the socioeconomic categories,
based on the property price of the home location and the relative age of the
mobile phone (a), and the number of the subscribers in each category (b).

###  4.7 Limitations

As the activity curves do not reach their maxima immediately, the selected
time does not accurately represent the neither the wake-up time, nor the time
when the working hours actually start. These results can only be used
relatively to other cells, or areas of the city. The reason of this, is that
the CDR s in this study only represents the active (in other word, billed)
usage of the mobile phone network. However, the employees usually do not
actively use the network at the moment they arrived to their workplace or
home. There is a certain gap between that moment and the first activity. If
the available data also contained the passive (cell-switching) communication,
the time, when a SIM card enter the home or work cell, could be used. In this
case, the terms “leaving home” and “arriving to the workplace” would be more
accurate. Furthermore, the difference of the two could serve as a basis for a
precise travel time estimation.

As the active mobile phone network activity is sporadic, the majority of the
subscribers do not have enough activity records to trace back their daily
movement accurately enough to determine when they leave their homes or arrive
to their workplace. It is very common that, the subscribers do not have
activity at home before work. It would be necessary to have multiple activity
in the morning to select the first and last home activity at home, to conclude
when the subscriber tend to wake up and leave their home. As this is not
assured with this kind of data, this approach is not good for individual-level
analysis.

The phone price database does not contain launch prices (see Appendix B) and
the applied depreciation method is unknown. The results, utilizing the cell
phone price as a socioeconomic indicator, should be interpreted by keeping
that in mind.

###  4.8 Future Work

With the home and work locations, the distance can be determined, on the other
hand, the travel time is hard to estimate. The subscriber could use different
transportation modes, that have different time demands. Furthermore, without
cell-switching information, the time when the subscriber left the home cell
and arrived to the work call cannot be exactly determined. Using the worker or
inhabitant filtered activity curves — described in Section 4.4 —, the morning
fall (and the evening rise) of the home location activity, and the rise (and
the fall) of the work location activity can be calculated. Considering that
the work location activity rises when the workers are usually arrived, and the
home activity of the inhabitants drops when they usually left to work, the
difference of these values could be applied to estimate the travel time of a
group of subscribers. This would, naturally, require a larger number of
subscribers in every home–work cell pairs, or the locations should be
aggregated by base stations or even larger areas of the city.

Although, the “edge detection” method, used in this paper, gives reasonable
results to determine the positive and negative edge of the activity curve, it
would be worth to compare it with other approaches.

##  5 Conclusions

In this study, we introduced “wake-up time” as an indicator to describe the
behavior of a group of subscribers. Due to the sporadic nature of the mobile
phone network data, we grouped subscribers by home and work locations to
analyze their activity at these locations. By determining the rising and the
falling edge of the activity curve of the workers at each location, the
beginning, the ending, and the length of the working hours were estimated.
Tendencies between the starting and the ending time of the working hours at
the work locations were also presented. This indicator is used not only to
classify the groups of subscribers (inhabitant-based approach), but the parts
of Budapest (area-based approach), thus city parts can also be characterized
by chronotypes. This was demonstrated by real-life examples as the opening
hours of the malls, in Budapest, or by the late activity fall of the party
district.

Wake-up time as a proposed indicator was compared to common indicators, as
Radius of Gyration or Entropy, and clear negative correlation was found. On
workdays, both Radius of Gyration and Entropy values were higher, while the
wake-up times are lower. On holidays, quite the contrary. The correlation
between bedtime, the counterpart of the wake-up time, and the mobility metrics
was not that strong, but still considerable.

The day length, calculated as a difference of bedtime and wake-up time, was
found to be constant between the workdays and holidays: the start and the end
of the day is also shifted. On the other hand, the day length reflected to the
seasonal differences of the two data set: it was found that the days are
longer, from the perspective a mobile phone network, when there is more
daylight. The longer days are the reason of the delayed activity fall, as the
wake-up times found to be marginally affected by the earlier sunrise.

Using socioeconomic classes derived from housing prices at the home location,
mobile phone prices and the age of the cell phone, correlation between the
wake-up time and the socioeconomic status was also identified. The
subscribers, living in less expensive apartments get up earlier, and this
tendency holds true in respect of the mobile phones prices: subscribers, who
owns more expensive cell phones tend to get up later.

These results may help to analyze further the city structures, by identifying
“early bird” or “night owl” areas and possible connections between them. City
parts with early morning or late night activities may require different public
transport services, for example, and can aid the transportation infrastructure
planning. Business development could also benefit from the detailed insight of
the neighborhood chronotypes, especially with the associated information of
the home locations and the socioeconomic status of the subscribers.

The socioeconomic aspect of these findings can also contribute to better
understanding the social structure of an urban environments. In this regard,
further studies need to be made, possibly with detailed census data, to
evaluate the commuting and working habits of the different socioeconomic
classes.

## Author Contributions

Conceptualization, G.P; methodology, G.P.; software, G.P.; validation, G.P.;
formal analysis, G.P.; investigation, G.P.; resources, G.P. and I.F.; data
curation, G.P.; writing—original draft preparation, G.P.; writing—review and
editing, G.P.; visualization, G.P.; supervision, I.F.; project administration,
I.F.; funding acquisition, I.F. All authors have read and agreed to the
published version of the manuscript.

## Funding

This research supported by the project 2019-1.3.1-KK-2019-00007 and by the
Eötvös Loránd Research Network Secretariat under grant agreement no. ELKH
KÖ-40/2020.

## Data Availability

CDR and TAC data, used this study, are not publicly available due to third
party restrictions.

## Acknowledgments

The authors would like to thank Vodafone Hungary and 51Degrees for providing
the Call Detail Records and the Type Allocation Code database used in this
study. The estate price data are provided by the ingatlan.com estate selling
portal. For plotting the maps, OpenStreetMap data were used; these data are
copyrighted by the OpenStreetMap contributors and licensed under the Open Data
Commons Open Database License (ODbL).

## Conflicts of Interest

The authors declare no conflict of interest. The funders had no role in the
design of the study; in the collection, analyses, or interpretation of data;
in the writing of the manuscript, or in the decision to publish the results.

## Glossary

CDR

    Call Detail Record
HUF

    Hungarian forint
IMEI

    International Mobile Equipment Identity
OSM

    OpenStreetMap
POI

    Point of interest
SIM

    Subscriber Identity Module
SWC

    sleep wake cycle
TAC

    Type Allocation Code

##  Appendix A Party District

The so-called party district is not an official area of the city with definite
borders. Usually, the area, bounded by the Károly Boulevard (c), Király Street
(e), Erzsébet Boulevard (a) and Rákóczi Street (b) is referred as “party
district” (see Figure 22(a)). This area is famous for ruin pubs and nightlife,
which also involves that it is not the most active area early in the morning.
Actually, the vivid nightlife of downtown is not confined only to this area.
The Deák Ferenc Square (d), the northern side of the Király Street (e) and the
eastern side of the Erzsébet Boulevard (a) can also be considered part of the
party district.

Actually, how big is the party district? To answer this question, the points
of interest (POI) have been downloaded from the OpenStreetMap (OSM) in the
categories of “bar”, “pub”, “biergarten” and “nightclub”, using the OSM
terminology, and plotted to a map (see Figure 22(b)). There are 192 bars, 472
pubs, 12 beer gardens and 31 nightclubs in the displayed, 9 km by 9 km part of
Budapest, and the area from Figure 22(a) is also highlighted. Note that, the
POI s are queried in 2021, and cannot show the exact state of 2017. However,
only the tendencies are important, that did not change fundamentally in the
last decade. The concentration of bars and pubs are, indeed, the highest
within the highlighted “party district” area, but still very high on the whole
Pest-side of the downtown, and there are also three smaller groups on the
Buda-side of the city.

(a)

(b)

Figure 22: The borders of the party district (a), within District 7; and bars,
pubs, beer gardens and nightclubs in Budapest downtown (b), based on
OpenStreetMap data.

##  Appendix B iPhones

(a)

(b)

Figure 23:  Based on the “April 2017” dataset, the different iPhone models in
use are also displayed (a), and comparing Apple iPhone prices [46] with the
GSMArena-based source [49] (b). Versions with the lowest amount of storage
denoted by “budget”, and versions with the most expensive versions categorized
as “high-end”.

As Apple iPhones are considered a status symbol [16], it makes them suitable
to validate the phone price database [49], described in Section 2.3. Figure
23(a), shows the number of subscribers that exclusively use the certain iPhone
models, in the “April 2017” dataset. Using TAC values, it is not possible to
distinguish the iPhone models based on specification like storage. However, it
is clear, that the most expensive models (“Plus” versions) do not have
significant user base, in contrast with some older models like iPhone 4 and
iPhone 5 series.

The launch prices of the iPhone models, released until April 2017, are
obtained from [46]. Figure 23(b), compares the two sources. As there are
different versions of the certain models, a “budget” (with the lowest amount
of storage), and a “high-end” (the most expensive) versions are also
displayed. Although, GSMArena price property is supposed to be a launch price,
Figure 23(b), clearly shows that they are much lower than the original prices.
Moreover, the older the phone is, that lower the available prices are, except
for the first iPhone. It has to be noted, that GSMArena prices are in EUR,
whereas the ground truth prices are in USD, but this cannot cause the
difference. The results of this analysis implies, that the phone prices might
have depreciated.

## Glossary

CDR

    Call Detail Record
HUF

    Hungarian forint
IMEI

    International Mobile Equipment Identity
OSM

    OpenStreetMap
POI

    Point of interest
SIM

    Subscriber Identity Module
SWC

    sleep wake cycle
TAC

    Type Allocation Code

## References

  * [1] Rein Ahas, Anto Aasa, Siiri Silm and Margus Tiru  “Daily rhythms of suburban commuters’ movements in the Tallinn metropolitan area: Case study with mobile positioning data”  In _Transportation Research Part C: Emerging Technologies_ 18.1 Elsevier, 2010, pp. 45–54
  * [2] Rein Ahas et al.  “Using mobile positioning data to model locations meaningful to users of mobile phones”  In _Journal of urban technology_ 17.1 Taylor & Francis, 2010, pp. 3–27
  * [3] MM Al-Akaidi and H Ali  “Performance analysis of antenna sectorisation in cell breathing”  IET, 2003
  * [4] T Alakörkkö and J Saramäki  “Circadian rhythms in temporal-network connectivity”  In _Chaos: An Interdisciplinary Journal of Nonlinear Science_ 30.9 AIP Publishing LLC, 2020, pp. 093115
  * [5] Talayeh Aledavood, Sune Lehmann and Jari Saramäki  “Social network differences of chronotypes identified from mobile phone data”  In _EPJ Data Science_ 7.1 Springer Berlin Heidelberg, 2018, pp. 46
  * [6] Talayeh Aledavood et al.  “Daily rhythms in mobile telephone communication”  In _PloS one_ 10.9 Public library of Science San Francisco, CA USA, 2015, pp. e0138098
  * [7] Albert-Laszlo Barabasi  “The origin of bursts and heavy tails in human dynamics”  In _Nature_ 435.7039 Nature Publishing Group, 2005, pp. 207–211
  * [8] Hugo Barbosa et al.  “Uncovering the socioeconomic facets of human mobility”  In _arXiv preprint arXiv:2012.00838_ , 2020
  * [9] Kunal Bhattacharya and Kimmo Kaski  “Social physics: uncovering human behaviour from communication”  In _Advances in Physics: X_ 4.1 Taylor & Francis, 2019, pp. 1527723
  * [10] Kristi Bushman, Konstantinos Pelechrinis and Alexandros Labrinidis  “Effectiveness and compliance to social distancing during COVID-19”  In _arXiv preprint arXiv:2006.12720_ , 2020
  * [11] Visual Crossing Corporation  “Visual Crossing Weather (2016-2017)” (Online; accessed on 30 November 2021), 2021  URL: https://www.visualcrossing.com/
  * [12] Clémentine Cottineau and Maarten Vanhoof  “Mobile phone indicators and their relation to the socioeconomic organisation of cities”  In _ISPRS International Journal of Geo-Information_ 8.1 Multidisciplinary Digital Publishing Institute, 2019, pp. 19
  * [13] Balázs Cs Csáji et al.  “Exploring the mobility of mobile phone users”  In _Physica A: statistical mechanics and its applications_ 392.6 Elsevier, 2013, pp. 1459–1473
  * [14] Andrea Cuttone et al.  “Sensiblesleep: A bayesian model for learning sleep patterns from smartphone events”  In _PloS one_ 12.1 Public Library of Science San Francisco, CA USA, 2017, pp. e0169901
  * [15] Mi Diao, Yi Zhu, Joseph Ferreira Jr and Carlo Ratti  “Inferring individual daily activities from mobile phone traces: A Boston example”  In _Environment and Planning B: Planning and Design_ 43.5 SAGE Publications Sage UK: London, England, 2016, pp. 920–940
  * [16] Ravindra Dissanayake and Thustan Amarasuriya  “Role of brand identity in developing global brands: A literature based review on case comparison between Apple iPhone vs Samsung smartphone brands”  In _Research journal of business and management_ 2.3, 2015, pp. 430–440
  * [17] Won Do Lee, Matthias Qian and Tim Schwanen  “The association between socioeconomic status and mobility reductions in the early stage of England’s COVID-19 epidemic”  In _Health & Place_ Elsevier, 2021, pp. 102563
  * [18] Fabon Dzogang, Stafford Lightman and Nello Cristianini  “Circadian mood variations in Twitter content”  In _Brain and neuroscience advances_ 1 SAGE Publications Sage UK: London, England, 2017, pp. 2398212817744501
  * [19] Fred Espenak  “Solstices and Equinoxes: 2001 to 2050” (Online; accessed on 16 December 2021), 2018  URL: http://astropixels.com/ephemeris/soleq2001.html
  * [20] Barbara Furletti, Roberto Trasarti, Paolo Cintia and Lorenzo Gabrielli  “Discovering and understanding city events with big data: the case of rome”  In _Information_ 8.3 Multidisciplinary Digital Publishing Institute, 2017, pp. 74
  * [21] Song Gao et al.  “Association of mobile phone location data indications of travel and stay-at-home mandates with covid-19 infection rates in the us”  In _JAMA network open_ 3.9 American Medical Association, 2020, pp. e2020485–e2020485
  * [22] Mohammadhossein Ghahramani, MengChu Zhou and Chi Tin Hon  “Extracting significant mobile phone interaction patterns based on community structures”  In _IEEE Transactions on Intelligent Transportation Systems_ 20.3 IEEE, 2018, pp. 1031–1041
  * [23] Rahul Goel, Rajesh Sharma and Anto Aasa  “Understanding gender segregation through Call Data Records: An Estonian case study”  In _Plos one_ 16.3 Public Library of Science San Francisco, CA USA, 2021, pp. e0248212
  * [24] Marta C Gonzalez, Cesar A Hidalgo and Albert-Laszlo Barabasi  “Understanding individual human mobility patterns”  In _nature_ 453.7196 Nature publishing group, 2008, pp. 779
  * [25] Hendrik Hiir, Rajesh Sharma, Anto Aasa and Erki Saluveer  “Impact of Natural and Social Events on Mobile Call Data Records – An Estonian Case Study”  In _Complex Networks and Their Applications VIII_ Cham: Springer International Publishing, 2020, pp. 415–426
  * [26] Songhua Hu et al.  “A big-data driven approach to analyzing and modeling human mobility trend under non-pharmaceutical interventions during COVID-19 pandemic”  In _Transportation Research Part C: Emerging Technologies_ 124 Elsevier, 2021, pp. 102955
  * [27] Shan Jiang, Joseph Ferreira and Marta C Gonzalez  “Activity-based human mobility patterns inferred from mobile phone data: A case study of Singapore”  In _IEEE Transactions on Big Data_ 3.2 IEEE, 2017, pp. 208–219
  * [28] Hang-Hyun Jo, Márton Karsai, János Kertész and Kimmo Kaski  “Circadian pattern and burstiness in mobile phone communication”  In _New Journal of Physics_ 14.1 IOP Publishing, 2012, pp. 013055
  * [29] Hamid Khataee, Istvan Scheuring, Andras Czirok and Zoltan Neufeld  “Effects of social distancing on the spreading of COVID-19 inferred from mobile phone data”  In _Scientific Reports_ 11.1 Nature Publishing Group, 2021, pp. 1–9
  * [30] Kevin S Kung, Kael Greco, Stanislav Sobolevsky and Carlo Ratti  “Exploring universal patterns in human home-work commuting from mobile phone data”  In _PloS one_ 9.6 Public Library of Science San Francisco, USA, 2014, pp. e96180
  * [31] Laura Lotero, Rafael G Hurtado, Luis Mario Florı́a and Jesús Gómez-Gardeñes  “Rich do not rise early: spatio-temporal patterns in the mobility networks of different socio-economic classes”  In _Royal Society open science_ 3.10 The Royal Society, 2016, pp. 150654
  * [32] Lorenzo Lucchini et al.  “Living in a pandemic: changes in mobility routines, social activity and adherence to COVID-19 protective measures”  In _Scientific Reports_ 11.1 Nature Publishing Group, 2021, pp. 1–12
  * [33] Marco Mamei and Massimo Colonna  “Estimating attendance from cellular network data”  In _International Journal of Geographical Information Science_ 30.7 Taylor & Francis, 2016, pp. 1281–1301
  * [34] Marco Mamei et al.  “Evaluating origin–destination matrices obtained from CDR data”  In _Sensors_ 19.20 Multidisciplinary Digital Publishing Institute, 2019, pp. 4470
  * [35] Humberto T Marques-Neto et al.  “Understanding human mobility and workload dynamics due to different large-scale events using mobile phone data”  In _Journal of Network and Systems Management_ 26.4 Springer, 2018, pp. 1079–1100
  * [36] Daniel Monsivais et al.  “Seasonal and geographical impact on human resting periods”  In _Scientific reports_ 7.1 Nature Publishing Group, 2017, pp. 1–10
  * [37] Daniel Monsivais et al.  “Tracking urban human activity from mobile phone calling patterns”  In _PLoS computational biology_ 13.11 Public Library of Science San Francisco, CA USA, 2017, pp. e1005824
  * [38] National Media and Infocommunications Authority, Hungary  “A Nemzeti Média- és Hírközlési Hatóság mobilpiaci jelentése 2015. IV. – 2019. II. negyedév”, 2019  URL: http://nmhh.hu/document/208458/NMHH_mobilpiaci_jelentes_2015Q42019Q2.pdf
  * [39] Olivera Novović et al.  “Uncovering the Relationship between Human Connectivity Dynamics and Land Use”  In _ISPRS International Journal of Geo-Information_ 9.3 Multidisciplinary Digital Publishing Institute, 2020, pp. 140
  * [40] Luca Pappalardo et al.  “An analytical framework to nowcast well-being using mobile phone data”  In _International Journal of Data Science and Analytics_ 2.1-2 Springer, 2016, pp. 75–92
  * [41] Luca Pappalardo et al.  “Evaluation of home detection algorithms on mobile phone data using individual-level ground truth”  In _EPJ data science_ 10.1 Springer Berlin Heidelberg, 2021, pp. 29
  * [42] Luca Pappalardo et al.  “Returners and explorers dichotomy in human mobility”  In _Nature communications_ 6 Nature Publishing Group, 2015, pp. 8166
  * [43] Gergő Pintér and Imre Felde  “Analyzing the Behavior and Financial Status of Soccer Fans from a Mobile Phone Network Perspective: Euro 2016, a Case Study”  In _Information_ 12.11 Multidisciplinary Digital Publishing Institute, 2021, pp. 468
  * [44] Gergő Pintér and Imre Felde  “Evaluating the Effect of the Financial Status to the Mobility Customs”  In _ISPRS International Journal of Geo-Information_ 10.5 Multidisciplinary Digital Publishing Institute, 2021, pp. 328
  * [45] Gergó Pintér et al.  “Activity Pattern Analysis of the Mobile Phone Network During a Large Social Event”  In _2019 IEEE-RIVF International Conference on Computing and Communication Technologies (RIVF)_ , 2019, pp. 1–5  IEEE
  * [46] Emil Protalinski  “iPhone prices from the original to iPhone X” (Online; accessed on 14 February 2022), 2017  URL: https://venturebeat.com/2017/09/12/iphone-prices-from-the-original-to-iphone-x/
  * [47] Gustavo Romanillos et al.  “The city turned off: Urban dynamics during the COVID-19 pandemic based on mobile phone data”  In _Applied Geography_ 134 Elsevier, 2021, pp. 102524
  * [48] Assaf Rotman and Michael Shalev  “Using Location Data from Mobile Phones to Study Participation in Mass Protests”  In _Sociological Methods & Research_ SAGE Publications Sage CA: Los Angeles, CA, 2020, pp. 0049124120914926
  * [49] Mohit Sainani  “GSMArena Mobile Phone Devices” (Online; Accessed on 28 June 2020)  URL: https://www.kaggle.com/msainani/gsmarena-mobile-devices
  * [50] Chaoming Song, Zehui Qu, Nicholas Blumm and Albert-László Barabási  “Limits of predictability in human mobility”  In _Science_ 327.5968 American Association for the Advancement of Science, 2010, pp. 1018–1021
  * [51] Ahmad Ilderim Tokey  “Spatial association of mobility and COVID-19 infection rate in the USA: A county-level study using mobile phone location data”  In _Journal of Transport & Health_ 22 Elsevier, 2021, pp. 101135
  * [52] Vincent A Traag, Arnaud Browet, Francesco Calabrese and Frédéric Morlot  “Social event detection in massive mobile phone data using probabilistic location inference”  In _2011 IEEE Third International Conference on Privacy, Security, Risk and Trust and 2011 IEEE Third International Conference on Social Computing_ , 2011, pp. 625–628  IEEE
  * [53] Iñaki Ucar et al.  “News or social media? Socio-economic divide of mobile service consumption”  In _Journal of the Royal Society Interface_ 18.185 The Royal Society, 2021, pp. 20210350
  * [54] Maarten Vanhoof, Fernando Reis, Thomas Ploetz and Zbigniew Smoreda  “Assessing the quality of home detection from mobile phone data for official statistics”  In _arXiv preprint arXiv:1809.07567_ , 2018
  * [55] Maarten Vanhoof et al.  “Comparing regional patterns of individual movement using corrected mobility entropy”  In _Journal of Urban Technology_ 25.2 Taylor & Francis, 2018, pp. 27–61
  * [56] Salvatore Vilella, Daniela Paolotti, Giancarlo Ruffo and Leo Ferres  “News and the city: understanding online press consumption patterns through mobile data”  In _EPJ Data Science_ 9.1 Springer, 2020, pp. 1–18
  * [57] Elias Willberg, Olle Järv, Tuomas Väisänen and Tuuli Toivonen  “Escaping from cities during the covid-19 crisis: Using mobile phone data to trace mobility in finland”  In _ISPRS International Journal of Geo-Information_ 10.2 Multidisciplinary Digital Publishing Institute, 2021, pp. 103
  * [58] Faber Henrique Zacarias Xavier et al.  “Analyzing the workload dynamics of a mobile phone network in large scale events”  In _Proceedings of the first workshop on urban networking_ , 2012, pp. 37–42
  * [59] Yang Xu, Alexander Belyi, Iva Bojic and Carlo Ratti  “Human mobility and socioeconomic status: Analysis of Singapore and Boston”  In _Computers, Environment and Urban Systems_ 72 Elsevier, 2018, pp. 51–67
  * [60] Yang Xu et al.  “Understanding aggregate human mobility patterns using passive mobile phone location data: a home-based approach”  In _Transportation_ 42.4 Springer, 2015, pp. 625–646
  * [61] Taha Yasseri, Giovanni Quattrone and Afra Mashhadi  “Temporal analysis of activity patterns of editors in collaborative mapping project of OpenStreetMap”  In _Proceedings of the 9th International Symposium on Open Collaboration_ , 2013, pp. 1–4
  * [62] Taha Yasseri, Robert Sumi and János Kertész  “Circadian patterns of wikipedia editorial activity: A demographic analysis”  In _PloS one_ 7.1 Public Library of Science San Francisco, USA, 2012, pp. e30091
  * [63] Guilherme Augusto Zagatti et al.  “A trip to work: Estimation of origin and destination of commuting patterns in the main metropolitan regions of Haiti using CDR”  In _Development Engineering_ 3 Elsevier, 2018, pp. 133–165


# Multi-dimensional graph fractional Fourier transform and its application

Fang-Jia Yan and Bing-Zhao Li∗ This work was supported in part by the National
Natural Science Foundation of China under Grant 61671063.Fangjia Yan is with
the School of Mathematics and Statistics, Beijing Institute of Technology,
Beijing 102488, China (e-mail: fangjia$\\_$yan@bit.edu.cn).Bingzhao Li is with
the School of Mathematics and Statistics, Beijing Institute of Technology,
Beijing 102488, China, and also with Beijing Key Laboratory on MCAACI, Beijing
Institute of Technology, Beijing 102488, China (e-mail:
li$\\_$bingzhao@bit.edu.cn).

###### Abstract

Many multi-dimensional signals appear in the real world, such as digital
images and data that has spatial and temporal dimensions. How to show the
spectrum of these multi-dimensional signals correctly is a key challenge in
the field of graph signal processing. This paper investigates the novel
transform for multi-dimensional signals defined on Cartesian product graph and
studies several related properties. Our work includes: (i) defining the multi-
dimensional graph fractional Fourier transform (MGFRFT) based on Laplacian
matrix and adjacency matrix; (ii) exploring the advantages of MGFRFT in
processing multi-dimensional signals in terms of spectrum and computational
time; (iii) applying the proposed transform to data compression to highlight
the utility and effectiveness of it.

###### Index Terms:

Graph signal processing, graph Fourier transform, fractional Fourier
transform, multi-dimensional signal processing.

##  I Introduction

Utilizing the underlying structure in the data is the core of many signal
processing tasks. In many cases, data resides on irregular domains. To
describe the structure and interpret the complex relationships of network data
sets in non-Euclidean spaces, some fundamental signal processing methods have
been extended to graph signals [1, 2, 3, 4, 5, 6]. Graphs become an important
form of signal representation since they can be used to describe the geometry
and topology of this kind of signal. In recent years, graph signal analysis
has gained considerable attention, giving rise to the graph-based transforms
such as graph Fourier transform (GFT) [7, 8], graph filters [9, 10], sampling
and recovery on graphs [11, 12]. Judging from the existing research results,
GFT mainly includes two basic signal processing methods i.e. based on
Laplacian matrix and adjacency matrix.

Similar to the classical Fourier transform, it was shown that the GFT is
inadequate for describing some applications or dealing with their underlying
mathematical problems. As a result, the fractional Fourier transform (FRFT) on
graph has been introduced to address the shortcoming of the GFT [13, 14, 15,
16]. However, the spectral graph Fractional Fourier Transform (SGFRFT) and
graph fractional Fourier transform (GFRFT) fail to show the correct spectrum
of multi-dimensional (m-D) graph signals [13, 15]. Because the eigenvalues of
the graph Laplacian and the adjacency matrix act as the graph spectrum, in
particular, the spectral functions are not well-defined, i.e., multi-valued
when they have non-distinct eigenvalues [17]. Furthermore, given a graph, if
the node number of it is large, the signal processing operations defined on
this graph require more computational complexity. For example, the complexity
of the SGFRFT [15] using an eigendecomposition is $O(N^{3})$ for a graph with
N nodes. For better application to real data, it is urgent to find a new
transform.

To solve the aforementioned problems related to traditional SGFRFT and GFRFT,
we propose a transform that is suitable for multi-dimensional graph signal.
The paper is organized as follows. Section II overviews spectral graph theory
and the definition of Cartesian product graphs. Section III defines the multi-
dimensional graph fractional Fourier transform (MGFRFT). In addition, a
performance analysis shows that compared with the traditional method, the
spectrum accuracy and calculation efficiency of our new transform are
significantly improved. Finally, we apply MGFRFT to data compression to
clarify its application potentials in Section IV.

##  II Preliminaries

###  II-A Spectral graph theory

A weighted graph $\mathcal{G}=\\{\mathcal{V},\mathcal{E},W\\}$ consists of a
finite set of vertices $\mathcal{V}=\\{v_{0},\cdots,v_{N-1}\\}$, where
$N=|\mathcal{V}|$ is the number of nodes, a set of edges
$\mathcal{E}=\\{(i,j)|i,j\in\mathcal{V},j\sim
i\\}\subseteq\mathcal{V}\times\mathcal{V}$, and a weighted adjacency matrix
$W$. We assume that the graph is undirected with positive edge weights. The
non-normalized graph Laplacian is a symmetric difference operator
$\mathcal{L}=D-W$ [18], where $D$ is a diagonal degree matrix of
$\mathcal{G}$. Let $\\{\chi_{0},\chi_{1},\cdots,\chi_{N-1}\\}$ be the set of
orthonormal eigenvectors. Suppose that the corresponding Laplacian eigenvalues
are sorted as
$0=\lambda_{0}<\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{N-1}:=\lambda_{max}$.
We have $\mathcal{L}=\mathbf{\chi}\mathbf{\Lambda}\mathbf{\chi}^{H}$, where
$\mathbf{\chi}=[\chi_{0},\chi_{1},\cdots,\chi_{N-1}]$, and the diagonal matrix
is $\mathbf{\Lambda}=diag([\lambda_{0},\lambda_{1},\cdots,\lambda_{N-1}])$.
The superscript $H$ represents the Hermitian transpose operation.

The fractional order is introduced to the Laplacian operator [15]. The graph
fractional Laplacian operator $\mathcal{L}_{\alpha}$ is defined by
$\mathcal{L}_{\alpha}=\mathbf{\kappa}R\mathbf{\kappa}^{H}$, where $\alpha$ is
the fractional order, $0<\alpha\leq 1$, $\ell=0,1,\cdots,N-1$ [15]. Note that
$\mathbf{\kappa}=\begin{bmatrix}\kappa_{0},&\kappa_{1},&\cdots,&\kappa_{N-1}\end{bmatrix}={\chi}^{\alpha}$,
and
$R=\text{diag}({\begin{bmatrix}r_{0},&r_{1},&\cdots,&r_{N-1}\end{bmatrix}})=\mathbf{\Lambda}^{\alpha}$,
so that $r_{\ell}=\lambda_{\ell}^{\alpha}$. In the follow-up part of this
paper, computing the $\alpha$ power of a matrix always uses matrix power
function.

###  II-B Cartesian product graph

Cartesian product graph is a type of graph multiplication [19]. Consider two
graphs $\mathcal{G}_{1}=\\{\mathcal{V}_{1},\mathcal{E}_{1},W_{1}\\}$ and
$\mathcal{G}_{2}=\\{\mathcal{V}_{2},\mathcal{E}_{2},W_{2}\\}$. The graphs
$\mathcal{G}_{1}$, $\mathcal{G}_{2}$ are factor graphs of the Cartesian
product $\mathcal{G}_{1}\square\mathcal{G}_{2}$.
$\mathcal{G}_{1}\square\mathcal{G}_{2}$ to be the graph with vertex set
$\mathcal{V}_{1}\times\mathcal{V}_{2}$ and
$\mathcal{V}_{1}=\\{0,\cdots,N_{1}-1\\},\mathcal{V}_{2}=\\{0,\cdots,N_{2}-1\\}$.

The adjacency matrix $W_{1}\oplus W_{2}$ and Laplacian matrix
$\mathcal{L}_{1}\oplus\mathcal{L}_{2}$ of
$\mathcal{G}_{1}\square\mathcal{G}_{2}$ can be expressed by those of its
factor graphs.

$W_{1}\oplus W_{2}=W_{1}\otimes I_{N_{2}}+I_{N_{1}}\otimes W_{2},$ (1)
$\mathcal{L}_{1}\oplus\mathcal{L}_{2}=I_{N_{2}}\otimes\mathcal{L}_{1}+\mathcal{L}_{2}\otimes
I_{N_{1}},$ (2)

where $I_{n}$ is the identity matrix of size $n$ [20].

We give an example of Cartesian product graph using in graph signal
processing. In Fig. 1, the sensor network measurements are decomposed as the
Cartesian product of sensor network and time series.

Figure 1: Measurements of a sensor network.

(a) Original Signal

(b) Frequencies

(c) 2-D Frequencies

Figure 2: 2-D graph signal and its spectrum.

##  III Multi-dimensional graph fractional Fourier transform

In some cases, the spectrum is multi-valued in graph fractional domain. In
order to show the spectrum more correctly, the definitions of multi-
dimensional graph fractional Fourier transform (MGFRFT) based on Laplacian
matrix and adjacency matrix are proposed in this section. The advantages of
MGFRFT is also explored.

###  III-A Laplacian-based multi-dimensional graph fractional Fourier
transform

Given a natural number $m$, consider $m$ graphs
$\mathcal{G}_{i}=\\{\mathcal{V}_{i},\mathcal{E}_{i},W_{i}\\}$ with vertex set
$\mathcal{V}_{i}$ and $\mathcal{V}_{i}=\\{0,\cdots,N_{i}-1\\}$,
$i={1,2,\dots,m}$. $\mathcal{L}_{i}$ is the Laplacian matrix of
$\mathcal{G}_{i}$ and its eigendecomposition is
$\mathcal{L}_{i}=\mathbf{\chi}_{i}\mathbf{\Lambda}_{i}\mathbf{\chi}_{i}^{H}$.
The corresponding graph fractional Laplacian operator is

$\mathcal{L}_{\alpha}^{(i)}=\mathbf{\kappa}^{(i)}R^{(i)}(\mathbf{\kappa}^{(i)})^{H},$
(3)

where

$\mathbf{\kappa}^{(i)}=\begin{bmatrix}\kappa_{0}^{(i)},&\kappa_{1}^{(i)},&\cdots,&\kappa_{N_{i}-1}^{(i)}\end{bmatrix}={\chi}_{i}^{\alpha},$
(4)

and

$R^{(i)}=\text{diag}({\begin{bmatrix}r_{0}^{(i)},&r_{1}^{(i)},&\cdots,&r_{N_{i}-1}^{(i)}\end{bmatrix}})=\mathbf{\Lambda}_{i}^{\alpha}.$
(5)

These $m$ graphs form a Cartesian product graph
$\mathcal{G}_{1}\square\cdots\square\mathcal{G}_{m}$. Because the Cartesian
product graph

$\displaystyle\mathcal{G}_{1}\square\cdots\square\mathcal{G}_{m}=((\cdots(\mathcal{G}_{1}\square\mathcal{G}_{2})\cdots)\square\mathcal{G}_{m}),$
(6)

we have the following eigendecomposition of the fractional Laplacian operator
of $\mathcal{G}_{1}\square\cdots\square\mathcal{G}_{m}$:

$\displaystyle(\mathcal{L}_{\alpha}^{(1)}\oplus\cdots\oplus\mathcal{L}_{\alpha}^{(m)})\times$
(7)
$\displaystyle\begin{pmatrix}\kappa_{\ell_{1}}^{(1)}(0)\kappa_{\ell_{2}}^{(2)}(0)\dots\kappa_{\ell_{m}}^{(m)}(0)\\\
\kappa_{\ell_{1}}^{(1)}(0)\kappa_{\ell_{2}}^{(2)}(0)\dots\kappa_{\ell_{m}}^{(m)}(1)\\\
\vdots\\\
\kappa_{\ell_{1}}^{(1)}(N_{1}-1)\kappa_{\ell_{2}}^{(2)}(N_{2}-1)\dots\kappa_{\ell_{m}}^{(m)}(N_{m}-1)\end{pmatrix}$
$\displaystyle={}$
$\displaystyle(r_{\ell_{1}}^{(1)}+\cdots+r_{\ell_{m}}^{(m)})\times$
$\displaystyle\begin{pmatrix}\kappa_{\ell_{1}}^{(1)}(0)\kappa_{\ell_{2}}^{(2)}(0)\dots\kappa_{\ell_{m}}^{(m)}(0)\\\
\kappa_{\ell_{1}}^{(1)}(0)\kappa_{\ell_{2}}^{(2)}(0)\dots\kappa_{\ell_{m}}^{(m)}(1)\\\
\vdots\\\
\kappa_{\ell_{1}}^{(1)}(N_{1}-1)\kappa_{\ell_{2}}^{(2)}(N_{2}-1)\dots\kappa_{\ell_{m}}^{(m)}(N_{m}-1)\end{pmatrix}.$

Define a signal on a Cartesian product graph as a ”multi-dimensional signal”.
Using the eigenvalues and eigenfunctions of
$\mathcal{L}_{\alpha}^{(1)}\oplus\cdots\oplus\mathcal{L}_{\alpha}^{(m)}$ in
(7), we propose the Laplacian-based multi-dimensional graph fractional Fourier
transform (L-MGFRFT).

###### Definition 1

The L-MGFRFT of a m-dimensional signal $f$ on a Cartesian product graph
$\mathcal{G}_{1}\square\cdots\square\mathcal{G}_{m}$ is

$\displaystyle\widehat{f}_{\alpha}(\ell_{1}+\cdots+\ell_{m})$ (8)
$\displaystyle={}$
$\displaystyle\sum^{N_{1}}_{n_{1}=1}\sum^{N_{2}}_{n_{2}=1}\dots\sum^{N_{m}}_{n_{m}=1}f(n_{1},\dots,n_{m})(\kappa^{(1)}_{\ell_{1}}(n_{1}))^{*}\cdots(\kappa^{(m)}_{\ell_{m}}(n_{m}))^{*},$

for $\ell_{i}=0,1,\cdots,N_{i}-1$. And its inverse (IL-MGFRFT) is given by

$\displaystyle f(n_{1},\dots,n_{m})$ (9) $\displaystyle={}$
$\displaystyle\sum^{N_{1}}_{\ell_{1}=1}\sum^{N_{2}}_{\ell_{2}=1}\dots\sum^{N_{m}}_{\ell_{m}=1}\widehat{f}_{\alpha}(\ell_{1}+\cdots+\ell_{m})\kappa^{(1)}_{\ell_{1}}(n_{1})\cdots\kappa^{(m)}_{\ell_{m}}(n_{m}),$

for $n_{i}=0,1,\cdots,N_{i}-1$.

###  III-B Adjacency-based multi-dimensional graph fractional Fourier
transform

In addition to Laplacian-based method, there is another important method
related to adjacency matrix in graph signal processing. Using the same
Cartesian product graph as in Section III-A, the eigendecomposition of the
adjacency operator $W_{i}$ of graph $\mathcal{G}_{i}$ is
$W_{i}=\mathbf{V_{i}J_{W_{i}}V_{i}^{-1}}$. The eigendecomposition of adjacency
matrix $W_{1}\oplus\cdots\oplus W_{m}$ is

$\displaystyle W_{1}\oplus\cdots\oplus W_{m}$ (10) $\displaystyle=$
$\displaystyle\mathbf{(V_{1}\otimes\cdots\otimes V_{m})}\times$
$\displaystyle\mathbf{(\sum_{j=1}^{m}I_{N_{1}\dots N_{j-1}}\otimes
J_{W_{j}}\otimes I_{N_{j+1}\dots N_{m}})}\times$
$\displaystyle\mathbf{(V_{1}\otimes\cdots\otimes V_{m})^{-1}}.$

Using the above eigendecomposition, we define adjacency-based multi-
dimensional graph fractional Fourier transform (A-MGFRFT).

###### Definition 2

The A-MGFRFT of a m-dimensional signal $\mathbf{f}$ on a Cartesian product
graph $\mathcal{G}_{1}\square\cdots\square\mathcal{G}_{m}$ is

$\displaystyle\mathbf{\hat{f}_{\alpha}}={}$
$\displaystyle\mathbf{((V_{1}\otimes\cdots\otimes V_{m})^{-1})^{\alpha}f}.$
(11)

Its inverse (IA-MGFRFT) is given by

$\mathbf{f}=\mathbf{(V_{1}\otimes\cdots\otimes
V_{m})^{\alpha}}\mathbf{\hat{f}_{\alpha}}.$ (12)

Though the spectrum obtained by these two MGFRFTs is usually different for the
same graph signal $f$, the process of signal analysis is similar. Therefore,
we mainly focus the Laplacian method in this paper. As for the adjacency
method, we only give the definition.

###  III-C Advantage analysis

For a signal on Cartesian product graph, the proposed MGFRFTs provide the
following advantages over the traditional GFRFT and SGFRFT. We use the two-
dimensional transform based on Laplacian matrix as an example to illustrate
how the advantages are reflected in the graph signal processing.

As the spectrum of the multi-dimensional graph signal obtained by 1-D
transforms is often multi-valued at a specific frequency and the GFRFT and
SGFRFT can only show 1-d spectrum. These two traditional methods are not
suitable for multi-dimensional graph signals. In Fig 2, with $\alpha=0.9$, we
visually display the shortcoming of the SGFRFT and the advantage of L-MGFRFT.
Fig 2(a) is a random 2-D graph signal on the grid graph. In Fig 2(b), we see
that at certain frequencies, the spectrum is double-valued. We use red line to
give an example of double-valued spectrum. In Fig 2(c), all the spectrum are
single-valued, and we use the same red color to show that the double-valued
spectrum in Fig 2(b) can be identified and separated by our new transform.
MGFRFT can rearrange the 1-D spectrum obtained by the SGFRFT into the m-D
frequency domain, and provide the m-D spectrum of the signal. Therefore,
MGFRFT can solve the multi-valuedness of the spectral functions.

Another advantage that can not be ignored is time consumption. The Cartesian
product graph can represent multi-domain data effectively [19]. Whenever the
underlying graph can be decomposed into two or more factor graphs with fewer
nodes, the computational cost of these operations can be reduced
significantly. Considering a Cartesian product graph
$\mathcal{G}_{1}\square\mathcal{G}_{2}$, the MGFRFT costs
$O(N_{1}^{2}N_{2}+N_{1}N_{2}^{2})$ time, whereas the traditional SGFRFT costs
$O(N_{1}^{2}N_{2}^{2})$ on the same graph. When we use factor graphs
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ instead of the original graph to
calculate the eigendecomposition of the graph fractional Laplacian, it also
takes less time.

Figure 3: The $k$NN graph $S$ for weather observation station networks.

(a) Original Signal (b) MGFRFT Frequencies  (c) Compressed Signal

Figure 4: An illustration of the compression process. TABLE I: RE and PSNR for different compression parameters. $\alpha=0.95$ | $\gamma=0.02$ | $\gamma=0.05$ | $\gamma=0.10$ | $\gamma=0.15$ | $\gamma=0.20$ | $\gamma=0.25$ | $\gamma=0.30$
---|---|---|---|---|---|---|---
RE(%) | 10.49 | 8.56 | 7.00 | 5.97 | 5.18 | 4.52 | 3.96
PSNR(dB) | 86.49 | 88.25 | 90.11 | 91.67 | 93.15 | 94.46 | 95.83
$\alpha=0.85$ | $\gamma=0.02$ | $\gamma=0.05$ | $\gamma=0.10$ | $\gamma=0.15$ | $\gamma=0.20$ | $\gamma=0.25$ | $\gamma=0.30$
RE(%) | 18.52 | 15.65 | 12.99 | 11.15 | 9.69 | 8.48 | 7.43
PSNR(dB) | 89.10 | 86.80 | 85.11 | 85.59 | 86.93 | 88.20 | 89.60

##  IV Applications

To illustrate the effectiveness of the framework in MGFRFT, we consider an
application to data compression. Using public real-world data from National
Oceanic and Atmospheric Administration (NOAA)’s National Centers for
Environmental Information (NCEI), we randomly select 200 weather observation
stations and pick out temperature records in 2020. The data is available in
https://www.ncei.noaa.gov/data/global-summary-of-the-day/access/2020/.

The temperature records naturally form a path graph with 365 nodes, denoted by
$\mathcal{T}$. To construct a graph model for stations, we adopt $k$NN method
as shown in [21]. For each pair of stations, we compute the spherical distance
via latitudes and longitudes. Specifically, let $(\theta_{i},\phi_{i})$ and
$(\theta_{j},\phi_{j})$ be the coordinates for two stations $i$ and $j$ (in
radian measure). The spherical distance is defined by

$\displaystyle d_{ij}={}$
$\displaystyle\arccos\bigg{(}\cos(\theta_{1})\cos(\theta_{2})\cos(\phi_{1}-\phi_{2})+$
(13) $\displaystyle\sin(\theta_{1})\sin(\theta_{2})\bigg{)}$

Note that we drop the earth radius $R=6,357$km in the computation of spherical
distance since it will cause large precision error when we use the Gaussian
kernel.

Then we search the $k$-nearest-neighbors for each station based on the
spherical distance. The $k$NN graph $S$ is constructed by setting each node as
a station and a pair of nodes is connected iff they are neighbors. Fig. 3
shows the $k$NN graph where $k$ is set to be 5.

The weighted matrix $W$ is defined by substituting the spherical distances
into the Gaussian kernel. Let $i$ and $j$ be two nodes joined by an edge. The
weight $W_{ij}$ is set to be

$W_{ij}=\frac{\exp(-\frac{d_{ij}^{2}}{\sigma^{2}})}{\sqrt{\sum_{k\sim
i}\exp(-\frac{d_{ik}^{2}}{\sigma^{2}})}\sqrt{\sum_{k\sim
j}\exp(-\frac{d_{jk}^{2}}{\sigma^{2}})}}$ (14)

where $\sim$ denotes that two nodes are incident, and $\sigma^{2}$ is a preset
parameter.

The temperature data thus can be regarded as a signal $f$ on the product graph
$\mathcal{G}\square\mathcal{T}$ where each element $f(i,t)$ denotes the
temperature at station $i$ on day $t$. The compression process is performed as
follows. We compute the MGFRFT of $f$ using equation (8). Then we sort the
coefficients according to their absolute values. Let $0<\gamma<1$ be the
compression ratio. We retain $\gamma$ fraction of largest coefficients and set
remaining coefficients to be zero. Finally we perform the inverse MGFRFT on
the resulting coefficients. Fig. 4 presents a $10\times 10$ block of the
original temperature data and compressed temperature data.

Two quantities are used to measure the compression loss. Let $f_{com}$ be the
compressed signal. The relative error (RE) is defined by

$\text{RE}=\frac{\sum_{i\in\mathcal{G},t\in\mathcal{T}}|f(i,t)-f_{com}(i,t)|}{\sum_{i\in\mathcal{G},t\in\mathcal{T}}|f(i,t)|}.$
(15)

The peak signal-to-noise ratio (PSNR) is defined by

PSNR (16) $\displaystyle={}$ $\displaystyle
10\log_{10}\left(\frac{\max_{i\in\mathcal{G},t\in\mathcal{T}}|f_{com}(i,t)|^{2}}{\frac{1}{|\mathcal{G}||\mathcal{T}|}\sum_{i\in\mathcal{G},t\in\mathcal{T}}|f(i,t)-f_{com}(i,t)|^{2}}\right).$

We carry out various experiments with different compression ratio $\gamma$ and
transform fractional orders $\alpha$. The result is shown in Tab. I. The
results show that even for extremely small $\gamma$, the compression only
introduces a small relative error. Further, compared with the results shown in
[22], the MGFRFT provides better transform basis and yields smaller error.
Tuning the fractional order $\alpha$ is also helpful to get more plausible
compression.

##  V Conclusions

In this paper, an approach to multi-domain data is presented. First, two
different definitions of MGFRFT are proposed. Then to make implementations of
our new transforms suitable for processing multi-dimensional signals, we
compare the frequency obtained by one-dimensional transform and two-
dimensional transform visually. The results show that the spectrum of our
MGFRFT is well-defined, which avoids the double-valued spectrum of one-
dimensional transforms that sometimes occurs. Finally, the MGFRFT is applied
to data compression, using real-world data. The experiment reveals that
compression based on our new transform is more efficient.

## References

  * [1] E. Ceci and S. Barbarossa, “Graph signal processing in the presence of topology uncertainties,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 1558–1573, 2020.
  * [2] F. Gama, E. Isufi, G. Leus, and A. Ribeiro, “Graphs, convolutions, and neural networks: From graph filters to graph neural networks,” _IEEE Signal Processing Magazine_ , vol. 37, no. 6, pp. 128–138, 2020.
  * [3] M. W. Morency and G. Leus, “Graphon filters: Graph signal processing in the limit,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 1740–1754, 2021.
  * [4] L. Stankovic and E. Sejdić, _Vertex-frequency analysis of graph signals_. Springer International Publishing, 2019.
  * [5] A. Ortega, P. Frossard, J. Kovačević, J. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,” _Proceedings of the IEEE_ , vol. 106, no. 5, pp. 808–828, 2018.
  * [6] A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs: Frequency analysis,” _IEEE Transactions on Signal Processing_ , vol. 62, no. 12, pp. 3042–3054, 2014.
  * [7] J. Domingos and J. M. F. Moura, “Graph fourier transform: A stable approximation,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 4422–4437, 2020.
  * [8] A. Sandryhaila and J. M. F. Moura, “Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure,” _IEEE Signal Processing Magazine_ , vol. 31, no. 5, pp. 80–90, 2014.
  * [9] R. Ramakrishna, H. T. Wai, and A. Scaglione, “A user guide to low-pass graph signal processing and its applications: Tools and applications,” _IEEE Signal Processing Magazine_ , vol. 37, no. 6, pp. 74–85, 2020.
  * [10] J. Jiang, D. B. Tay, Q. Sun, and S. Ouyang, “Design of nonsubsampled graph filter banks via lifting schemes,” _IEEE Signal Processing Letters_ , vol. 27, pp. 441–445, 2020.
  * [11] S. Chen, A. Sandryhaila, J. M. F. Moura, and J. Kovačević, “Signal recovery on graphs: Variation minimization,” _IEEE Transactions on Signal Processing_ , vol. 63, no. 17, pp. 4609–4624, 2015.
  * [12] S. Chen, R. Varma, A. Sandryhaila, and J. Kovačević, “Discrete signal processing on graphs: Sampling theory,” _IEEE Transactions on Signal Processing_ , vol. 63, no. 24, pp. 6510–6523, 2015.
  * [13] Y. Wang, B. Li, and Q. Cheng, “The fractional fourier transform on graphs,” in _2017 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC)_. IEEE, 2017, pp. 105–110.
  * [14] Y. Wang and B. Li, “The fractional fourier transform on graphs: Sampling and recovery,” in _2018 14th IEEE International Conference on Signal Processing (ICSP)_. IEEE, 2018, pp. 1103–1108.
  * [15] J. Wu, F. Wu, Q. Yang, Y. Zhang, X. Liu, Y. Kong, L. Senhadji, and H. Shu, “Fractional spectral graph wavelets and their applications,” _Mathematical Problems in Engineering_ , vol. 2020, 2020.
  * [16] F. Yan, W. Gao, and B. Li, “Windowed fractional fourier transform on graphs: Fractional translation operator and hausdorff-young inequality,” in _2020 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC)_. IEEE, 2020, pp. 255–259.
  * [17] T. Kurokawa, T. Oki, and H. Nagao, “Multi-dimensional graph fourier transform,” _arXiv preprint arXiv:171207811_ , 2017.
  * [18] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,” _IEEE Signal Processing Magazine_ , vol. 30, no. 3, pp. 83–98, 2013.
  * [19] W. Imrich, S. Klavzar, and D. F. Rall, _Topics in graph theory: Graphs and their Cartesian product_. CRC Press, 2008\.
  * [20] S. K. Kadambari and S. P. Chepuri, “Learning product graphs from multidomain signals,” in _2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2020.
  * [21] A. P. Sanil, _Principles of Data Mining_. Kluwer Academic Publishers, 2003.
  * [22] A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs: Graph fourier transform,” in _2013 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2013, pp. 6167–6170.